Tutorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, L, a;
int t[maxn], l[maxn];
int main(){
scanf("%d%d%d", &n, &L, &a);
for(int i = 0; i < n; i++){
scanf("%d%d", &t[i], &l[i]);
}
int start = 0;
int ans = 0;
for(int i = 0; i < n; i++){
ans += (t[i] - start)/a;
start = t[i] + l[i];
}
ans += (L - start)/a;
printf("%d", ans);
return 0;
}
Tutorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn = (int)1e3 + 3;
int n, m;
char a[maxn][maxn];
bool can[maxn][maxn];
vector<int> must_have[maxn][maxn];
inline bool inside(int x, int y){
return x >= 0 && y >= 0 && x < n && y < m;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
can[i][j] = true;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
do{
a[i][j] = getc(stdin);
}while(a[i][j] != '.' && a[i][j] != '#');
for(int dx = -1; dx <= 1; dx++)
for(int dy = -1; dy <= 1; dy++){
if(abs(dx) + abs(dy) == 0 || !inside(i + dx, j + dy))continue;
if(a[i][j] == '.')can[i + dx][j + dy] = false;
else if (i + dx != 0 && j + dy != 0 && i + dx != n - 1 && j + dy != m - 1)must_have[i][j].push_back((i + dx) * m + j + dy);
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
bool good = false;
if(a[i][j] == '.')continue;
for(int cand : must_have[i][j]){
int x = cand/m, y = cand%m;
good |= can[x][y];
}
if(!good){printf("NO"); return 0;}
}
printf("YES");
return 0;
}
1059C - Sequence Transformation
Tutorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 6;
int seq[maxn];
int ans[maxn];
int ptr = 0;
void solve(int n, int mul){
if(n == 1){ans[ptr++] = mul; return;}
if(n == 2){ans[ptr++] = mul; ans[ptr++] = mul * 2; return;}
if(n == 3){ans[ptr++] = mul; ans[ptr++] = mul; ans[ptr++] = mul * 3; return;}
for(int i = 0; i < n; i++)if(seq[i]&1)ans[ptr++] = mul;
for(int i = 0; i < n/2; i++)seq[i] = seq[2*i + 1]/2;
solve(n/2, mul * 2);
}
int main(){
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)seq[i] = i + 1;
solve(n, 1);
for(int i = 0; i < n; i++)printf("%d ", ans[i]);
return 0;
}
Tutorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
typedef long double dbl;
const dbl eps = 1e-9;
inline bool gt(const dbl & x, const dbl & y){
return x > y + eps;
}
inline bool lt(const dbl & x, const dbl & y){
return y > x + eps;
}
inline dbl safe_sqrt(const dbl & D){
return D < 0 ? 0 : sqrt(D);
}
struct pt{
dbl x, y;
pt(){}
pt(dbl a, dbl b):x(a), y(b){}
};
const int N = 1e5 + 5;
const int STEPS = 150;
int n;
pt p[N];
inline bool can(dbl R){
dbl l = -1e16 - 1, r = 1e16 + 1;
for(int i = 0; i < n; i++){
dbl b = -2 * p[i].x;
dbl c = p[i].x * p[i].x + p[i].y * p[i].y - 2 * p[i].y * R;
dbl D = b * b - 4 * c;
if(lt(D, 0))
return false;
D = safe_sqrt(D);
dbl x1 = p[i].x - D/2, x2 = p[i].x + D/2;
l = max(l, x1);
r = min(r, x2);
}
return !gt(l, r);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
bool has_positive = false, has_negative = false;
for(int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
p[i] = pt(x, y);
if(y > 0)has_positive = true;
else has_negative = true;
}
if(has_positive && has_negative){
cout << -1 << endl;
return 0;
}
if(has_negative){
for(int i = 0; i < n; i++)
p[i].y = -p[i].y;
}
dbl L = 0, R = 1e16;
std::function<dbl(dbl, dbl)> get_mid;
if(can(1)){
R = 1;
get_mid = [](dbl l, dbl r){return (l + r)/2.0;};
}
else{
L = 1;
get_mid = [](dbl l, dbl r){return sqrt(l * r);};
}
for(int step = 0; step < STEPS; step++){
dbl mid = get_mid(L, R);
if(can(mid))
R = mid;
else
L = mid;
}
cout.precision(16);
cout << fixed << get_mid(L, R) << endl;
}
Tutorial
Tutorial is loading...
Code (first solution)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int lg = 20;
const ll inf = 1e18;
int n, L;
ll S;
ll t[4 * maxn];
ll t_add[4 * maxn];
int cid = 0;
int w[maxn];
vector<int> down[maxn];
ll sum[maxn];
int up[maxn];
int p[maxn][lg];
ll dp[maxn];
int id[maxn], rb[maxn];
ll dp_sum[maxn];
vector<int> rm[maxn];
inline ll get_sum(int v){
return v == -1 ? 0 : sum[v];
}
void preprocess(int v, int pr = -1){
sum[v] = get_sum(pr) + w[v];
p[v][0] = pr;
up[v] = v;
id[v] = rb[v] = cid++;
for(int i = 1; i < lg; i++)
p[v][i] = p[v][i - 1] == -1 ? -1 : p[p[v][i - 1]][i - 1];
int dist = L - 1;
for(int i = lg - 1; i >= 0; i--){
if(p[up[v]][i] == -1 || (1<<i) > dist)continue;
if(get_sum(v) - get_sum(p[up[v]][i]) + w[p[up[v]][i]] <= S){
dist -= 1<<i;
up[v] = p[up[v]][i];
}
}
rm[up[v]].push_back(v);
for(int u : down[v]){
preprocess(u, v);
rb[v] = max(rb[v], rb[u]);
}
}
inline void push(int v){
t[2*v] += t_add[v];
t[2*v + 1] += t_add[v];
t_add[2*v] += t_add[v];
t_add[2*v + 1] += t_add[v];
t_add[v] = 0;
}
void build_tree(int v, int l, int r){
t[v] = inf;
if(l == r)
return;
int mid = (l + r)/2;
build_tree(2*v, l, mid);
build_tree(2*v + 1, mid + 1, r);
}
ll get_tree(int v, int l, int r, int ul, int ur){
if(ul > ur)
return inf;
if(l == ul && r == ur)
return t[v];
push(v);
int mid = (l + r)/2;
return min(get_tree(2*v, l, mid, ul, min(ur, mid)), get_tree(2*v + 1, mid + 1, r, max(ul, mid + 1), ur));
}
void set_tree(int v, int l, int r, int pos, ll val){
if(l == r){
t[v] = val;
return;
}
push(v);
int mid = (l + r)/2;
if(pos <= mid)
set_tree(2*v, l, mid, pos, val);
else
set_tree(2*v + 1, mid + 1, r, pos, val);
t[v] = min(t[2*v], t[2*v + 1]);
}
void add_tree(int v, int l, int r, int ul, int ur, ll val){
if(ul > ur)return;
if(l == ul && r == ur){
t[v] += val;
t_add[v] += val;
return;
}
push(v);
int mid = (l + r)/2;
add_tree(2*v, l, mid, ul, min(ur, mid), val);
add_tree(2*v + 1, mid + 1, r, max(ul, mid + 1), ur, val);
t[v] = min(t[2*v], t[2*v + 1]);
}
inline void upd(int v){
dp[v] = 1 + get_tree(1, 0, n - 1, id[v], rb[v]);
}
inline void add(int v){
set_tree(1, 0, n - 1, id[v], 0);
add_tree(1, 0, n - 1, id[v], rb[v], dp_sum[v] - dp[v]);
}
inline void remove(int v){
set_tree(1, 0, n - 1, id[v], inf);
}
void solve(int v){
for(int u : down[v]){
solve(u);
dp_sum[v] += dp[u];
}
add(v);
dp[v] = maxn;
upd(v);
add_tree(1, 0, n - 1, id[v], rb[v], -dp[v]);
for(int u : rm[v])
remove(u);
}
int main(){
scanf("%d%d%lld", &n, &L, &S);
for(int i = 0; i < n; i++){
scanf("%d", &w[i]);
if(w[i] > S){printf("-1"); return 0;}
}
for(int i = 1; i < n; i++){
int j;
scanf("%d", &j);
down[--j].push_back(i);
}
preprocess(0);
build_tree(1, 0, n - 1);
solve(0);
printf("%lld", dp[0]);
}
Code (second solution)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int lg = 20;
const ll inf = 1e18;
int n, L;
ll S;
int w[maxn];
vector<int> down[maxn];
ll sum[maxn];
int up[maxn];
int h[maxn];
int p[maxn][lg];
int path[maxn];
inline ll get_sum(int v){
return v == -1 ? 0 : sum[v];
}
void preprocess(int v, int pr = -1){
sum[v] = get_sum(pr) + w[v];
p[v][0] = pr;
h[v] = pr == -1 ? 0 : (1 + h[pr]);
up[v] = v;
for(int i = 1; i < lg; i++)
p[v][i] = p[v][i — 1] == -1 ? -1 : p[p[v][i — 1]][i — 1];
int dist = L — 1;
for(int i = lg — 1; i >= 0; i--){
if(p[up[v]][i] == -1 || (1<<i) > dist)continue;
if(get_sum(v) — get_sum(p[up[v]][i]) + w[p[up[v]][i]] <= S){
dist -= 1<<i;
up[v] = p[up[v]][i];
}
}
for(int u : down[v]){
preprocess(u, v);
}
}
int solve(int v){
int ans = 0;
int best = -1;
for(int u : down[v]){
ans += solve(u);
if(path[u] == u)continue;
if(best == -1 || h[best] > h[path[u]])
best = path[u];
}
if(best == -1){
best = up[v];
++ans;
}
path[v] = best;
return ans;
}
int main(){
scanf("%d%d%lld", &n, &L, &S);
for(int i = 0; i < n; i++){
scanf("%d", &w[i]);
if(w[i] > S){printf("-1"); return 0;}
}
for(int i = 1; i < n; i++){
int j;
scanf("%d", &j);
down[--j].push_back(i);
}
preprocess(0);
printf("%d", solve(0));
}