# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
49918 | mra2322001 | Monkey and Apple-trees (IZhO12_apple) | C++14 | 579 ms | 150944 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i<(n); i++)
#define f1(i, n) for(int i(1); i<=(n); i++)
using namespace std;
typedef long long ll;
const int NODE = 2e6 + 2e5;
const int N = 1000000000;
struct node{
int l, r, sum, add;
node(){
l = r = sum = add = 0;
}
} t[NODE*4];
int c, cnt = 1;
void push(int k, int l, int r){
if(t[k].add){
if(t[k].l==0) t[k].l = ++cnt;
if(t[k].r==0) t[k].r = ++cnt;
t[t[k].l].add = 1;
t[t[k].r].add = 1;
t[k].sum = (r - l + 1);
t[k].add = 0;
}
}
void up(int k, int l, int r, int u, int v){
push(k, l, r);
if(r < u || l > v) return ;
if(l >= u && r <= v){
t[k].add = 1;
t[k].sum = (r - l + 1);
return ;
}
int m = (l + r)/2;
if(t[k].l==0) t[k].l = ++cnt;
if(t[k].r==0) t[k].r = ++cnt;
up(t[k].l, l, m, u, v);
up(t[k].r, m + 1, r, u, v);
t[k].sum = t[t[k].l].sum + t[t[k].r].sum;
}
int get1(int k, int l, int r, int u, int v){
push(k, l, r);
if(r < u || l > v) return 0;
if(l >= u && r <= v) return t[k].sum;
int m = (l + r)/2;
int res = 0;
if(t[k].l){ /// neu khong co t[k].l thi nghia la no chua duoc update(de len tao chin do) lan nao ca => res = 0 khong can suy nghi, vi
/// lam the moi tiet kiem duoc bo nho
res += (get1(t[k].l, l, m, u, v));
}
if(t[k].r){
res += get1(t[k].r, m + 1, r, u, v);
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
int m; cin >> m;
while(m--){
int ty, u, v; cin >> ty >> u >> v;
u += c, v += c;
if(ty==1){
int x = c;
c = get1(1, 1, N, u, v);
cout << c << endl;
}
else up(1, 1, N, u, v);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |