# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1001047 | rahidilbayramli | Monkey and Apple-trees (IZhO12_apple) | C++17 | 222 ms | 191376 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 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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |