/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(x...)
#endif
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define rrep(a, b, c) for(int a = (b); a > c; --a)
#define each(a, b) for(auto& a : b)
#define sz(x) (int)(x).size()
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vi vector<int>
#define ar array
template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define rsz resize
#define bk back()
#define pi pair<int, int>
#define pl pair<ll, ll>
#define mp make_pair
#define f first
#define s second
#define pct(x) __builtin_popcount(x)
constexpr int fsb(int x) {return __builtin_ffs(x) - 1;} // first set bit
constexpr int log2(int x) {return x == 0 ? 0 : 31-__builtin_clz(x);} // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
using ll = long long;
using ld = long double;
using str = string;
const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const ld PI = acos((ld)-1);
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/
const int SZ = 1<<30;
template<class T> struct node {
T val = 0; node<T>* c[2]; bool ok = 0;
node() { c[0] = c[1] = NULL; }
void upd(int l, int r, int L = 0, int R = SZ-1) { // add v
if(R < l || L > r || ok) return;
if (l <= L && R <= r) {
ok = 1;
val = R - L + 1; return;
}
int M = (L+R)/2;
if (!c[0]) c[0] = new node();
c[0]->upd(l,r,L,M);
if (!c[1]) c[1] = new node();
c[1]->upd(l,r,M+1,R);
val = 0; rep(i, 0, 2) val += c[i]->val;
}
T query(int lo, int hi, int L = 0, int R = SZ-1) { // query sum of segment
if (hi < L || R < lo) return 0;
if (lo <= L && R <= hi) return val;
if(ok) return min(R, hi) - max(lo, L) + 1;
int M = (L+R)/2; T res = 0;
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);
}
};
node<int> rt;
void solve(){
int q; cin >> q;
int c = 0;
while(q--){
int t, a, b; cin >> t >> a >> b;
a += c; b += c;
if(t&1){
c = rt.query(a, b);
cout << c << '\n';
}else{
rt.upd(a, b);
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
| # |
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 |
Correct |
6 ms |
452 KB |
Output is correct |
| 5 |
Correct |
5 ms |
460 KB |
Output is correct |
| 6 |
Correct |
5 ms |
468 KB |
Output is correct |
| 7 |
Correct |
5 ms |
468 KB |
Output is correct |
| 8 |
Correct |
23 ms |
1468 KB |
Output is correct |
| 9 |
Correct |
39 ms |
2436 KB |
Output is correct |
| 10 |
Correct |
39 ms |
2424 KB |
Output is correct |
| 11 |
Correct |
36 ms |
2424 KB |
Output is correct |
| 12 |
Correct |
36 ms |
2480 KB |
Output is correct |
| 13 |
Correct |
47 ms |
2764 KB |
Output is correct |
| 14 |
Correct |
49 ms |
2876 KB |
Output is correct |
| 15 |
Correct |
36 ms |
2976 KB |
Output is correct |
| 16 |
Correct |
36 ms |
2928 KB |
Output is correct |
| 17 |
Correct |
47 ms |
2792 KB |
Output is correct |
| 18 |
Correct |
52 ms |
2764 KB |
Output is correct |
| 19 |
Correct |
35 ms |
2940 KB |
Output is correct |
| 20 |
Correct |
35 ms |
2948 KB |
Output is correct |
