Submission #1001047

#TimeUsernameProblemLanguageResultExecution timeMemory
1001047rahidilbayramliMonkey and Apple-trees (IZhO12_apple)C++17
0 / 100
222 ms191376 KiB
#include<bits/stdc++.h> #define ll int #define ld long double #define vl vector<ll> #define vi vector<int> #define pii pair<int, int> #define pll pair<ll, ll> #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define f first #define s second #define pb push_back #define p_b pop_back using namespace std; const ll sz = 6e6+7; ll L[sz], R[sz], segtree[sz], lazy[sz], nxt = 1; void push(ll v, ll l, ll r) { if(lazy[v] != 0) { segtree[v] = (r - l + 1); if(l != r) { if(!L[v]) L[v] = ++nxt; if(!R[v]) R[v] = ++nxt; lazy[L[v]] = 1; lazy[R[v]] = 1; } lazy[v] = 0; } } void update(ll v, ll l, ll r, ll tl, ll tr) { push(v, l, r); if(l > r || l > tr || r < tl) return; if(tl <= l && r <= tr) { segtree[v] = (r - l + 1); if(l != r) { if(!L[v]) L[v] = ++nxt; if(!R[v]) R[v] = ++nxt; lazy[L[v]] = 1; lazy[R[v]] = 1; } return; } ll mid = (l + r) / 2; if(!L[v]) L[v] = ++nxt; if(!R[v]) R[v] = ++nxt; update(L[v], l, mid, tl, tr); update(R[v], mid+1, r, tl, tr); segtree[v] = segtree[L[v]] + segtree[R[v]]; } ll findsum(ll v, ll l, ll r, ll tl, ll tr) { if(l > r || l > tr || r < tl) return 0; push(v, l, r); if(tl <= l && r <= tr) return segtree[v]; else { ll mid = (l + r) / 2; ll lans = 0, rans = 0; if(L[v]) lans = findsum(L[v], l, mid, tl, tr); if(R[v]) rans = findsum(R[v], mid+1, r, tl, tr); return lans + rans; } } void solve() { ll n = 1e9+7, m, i, c = 0; cin >> m; for(i = 1; i <= m; i++) { ll type; cin >> type; if(type == 2){ ll l, r; cin >> l >> r; l += c, r += c; update(1, 1, n, l, r); } else{ ll l, r; cin >> l >> r; l += c, r += c; c = findsum(1, 1, n, l, r); cout << c << "\n"; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll tests = 1; //cin >> tests; while(tests--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...