#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
#define ook order_of_key
#define fbo find_by_order
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<long long> vll;
#define PI acos(-1.0)
#define EPS 1e-9
#define INF 1000000000
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define pb push_back
#define mkp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define FOR(i, l, r) for(int i=int(l); i<=int(r); i++)
#define ROF(i, l, r) for(int i=int(r); i>=int(l); --i)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7;
void print_out(int x){
cout<<"Case #"<<x<<": ";
}
const int SZ = 1<<30;
template<class T> struct node {
T val = 0, lazy=0; node<T>* c[2];
node() { c[0] = c[1] = NULL; }
void push(int L, int R){
if(lazy==0)return;
val = (R-L+1)*lazy;
if(L!=R){
if(!c[0])c[0] = new node();
if(!c[1])c[1] = new node();
c[0]->lazy = lazy;
c[1]->lazy = lazy;
}
lazy = 0;
}
void upd(int lo, int hi, T v, int L = 0, int R = SZ-1) { // add v
push(L, R);
if(hi<L || R<lo)return;
if (lo<=L && R<=hi) { lazy = v; push(L, R); return; }
int M = (L+R)/2;
if(!c[0])c[0] = new node();
if(!c[1])c[1] = new node();
c[0]->upd(lo, hi, v, L, M);
c[1]->upd(lo, hi, v, M+1, R);
val = 0; FOR(i,0, 1) if (c[i]) val += c[i]->val;
}
T query(int lo, int hi, int L = 0, int R = SZ-1) { // query sum of segment
push(L, R);
if (hi < L || R < lo) return 0;
if (lo <= L && R <= hi) return val;
int M = (L+R)/2; T res = 0;
if (c[0]!=NULL) res += c[0]->query(lo,hi,L,M);
if (c[1]!=NULL) res += c[1]->query(lo,hi,M+1,R);
return res;
}
void UPD(int ind, node* c0, node* c1, int L = 0, int R = SZ-1) { // for 2D segtree
if (L != R) {
int M = (L+R)/2;
if (ind <= M) {
if (!c[0]) c[0] = new node();
c[0]->UPD(ind,c0?c0->c[0]:NULL,c1?c1->c[0]:NULL,L,M);
} else {
if (!c[1]) c[1] = new node();
c[1]->UPD(ind,c0?c0->c[1]:NULL,c1?c1->c[1]:NULL,M+1,R);
}
}
val = (c0?c0->val:0)+(c1?c1->val:0);
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int m; cin>>m;
node<int>* seg = new node<int>();
int c = 0;
FOR(i, 0, m-1){
int d, x, y;cin>>d>>x>>y;
if(d==1){
c = seg->query(x+c-1, y+c-1);
cout<<c<<"\n";
}
else{
seg->upd(x+c-1, y+c-1, 1);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
14 ms |
5720 KB |
Output is correct |
| 5 |
Correct |
19 ms |
6900 KB |
Output is correct |
| 6 |
Correct |
19 ms |
6680 KB |
Output is correct |
| 7 |
Correct |
18 ms |
6860 KB |
Output is correct |
| 8 |
Correct |
142 ms |
49840 KB |
Output is correct |
| 9 |
Correct |
290 ms |
87884 KB |
Output is correct |
| 10 |
Correct |
301 ms |
94712 KB |
Output is correct |
| 11 |
Correct |
313 ms |
102884 KB |
Output is correct |
| 12 |
Correct |
323 ms |
106312 KB |
Output is correct |
| 13 |
Correct |
304 ms |
134324 KB |
Output is correct |
| 14 |
Correct |
303 ms |
135692 KB |
Output is correct |
| 15 |
Correct |
503 ms |
246856 KB |
Output is correct |
| 16 |
Correct |
508 ms |
248700 KB |
Output is correct |
| 17 |
Correct |
317 ms |
140256 KB |
Output is correct |
| 18 |
Correct |
307 ms |
140380 KB |
Output is correct |
| 19 |
Correct |
512 ms |
256612 KB |
Output is correct |
| 20 |
Correct |
525 ms |
256724 KB |
Output is correct |
