#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<<17;
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){
val = (R-L+1)*lazy;
if(L!=R){
FOR(i, 0, 1){
if(!c[i])c[i] = new node();
c[i]->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 (hi <= M) {
if (!c[0]) c[0] = new node();
c[0]->upd(lo, hi,v, L,M);
} else if(lo>M){
if (!c[1]) c[1] = new node();
c[1]->upd(lo, hi,v, M+1,R);
}
else{
if(!c[0])c[0] = new node();
c[0]->upd(lo, hi, v, L, M);
if(!c[1])c[1] = new node();
c[1]->upd(lo, hi, v, M+1, R);
}
if(c[0])c[0]->push(L, M);
if(c[1])c[1]->push(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])c[0] = new node();
if(!c[1])c[1] = new node();
if (c[0]) res += c[0]->query(lo,hi,L,M);
if (c[1]) 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, y+c);
cout<<c<<"\n";
}
else{
seg->upd(x+c, y+c, 1);
}
}
return 0;
}
Compilation message
apple.cpp: In member function 'void node<T>::upd(int, int, T, int, int)':
apple.cpp:77:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
77 | if(c[1])c[1]->push(M+1, R);
| ^~
apple.cpp:79:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
79 | val = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
1136 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
