Submission #502412

# Submission time Handle Problem Language Result Execution time Memory
502412 2022-01-05T21:52:31 Z reni Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
298 ms 137540 KB
#include<iostream>
#define endl '\n'
#include<bits/stdc++.h>
using namespace std;
struct str
{
    int l=0, r=0, lazy=0, sum=0;
}tree[10000005];
int last=2;
void update(int le,int ri,int l,int r,int ind)
{
    if(!tree[ind].l)tree[ind].l=last++;
    if(!tree[ind].r)tree[ind].r=last++;

    if(l<=le && ri<=r){tree[ind].lazy=1;}

    if(tree[ind].lazy)
    {
        tree[ind].sum=(ri-le+1);

        tree[tree[ind].l].lazy=1;
        tree[tree[ind].r].lazy=1;

        tree[ind].lazy=0;
    }
    if(l>ri || r<le)return;
    if(l<=le && ri<=r)return;

    int mid=(le+ri)/2;

    update(le,mid,l,r,tree[ind].l);
    update(mid+1,ri,l,r,tree[ind].r);

    tree[ind].sum=tree[tree[ind].l].sum+tree[tree[ind].r].sum;


}
int query(int le,int ri,int l,int r,int ind)
{

    if(!tree[ind].l)tree[ind].l=last++;
    if(!tree[ind].r)tree[ind].r=last++;

    if(tree[ind].lazy)
    {
        tree[ind].sum=(ri-le+1);

        tree[tree[ind].l].lazy=1;
        tree[tree[ind].r].lazy=1;

        tree[ind].lazy=0;
    }
    if(l<=le && ri<=r){return tree[ind].sum;}

    if(l>ri || r<le)return 0;

    int mid=(le+ri)/2;

    int r1=0, r2=0;

    if(tree[ind].l)r1=query(le,mid,l,r,tree[ind].l);
    if(tree[ind].r)r2=query(mid+1,ri,l,r,tree[ind].r);

    tree[ind].sum=tree[tree[ind].l].sum+tree[tree[ind].r].sum;

    return r1+r2;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int i,j,t,l,r,m,c=0;

    cin>>m;

    for(i=0;i<m;i++)
    {
        cin>>t>>l>>r;

        l+=c; r+=c;

        if(t==2)
        {
            update(1,1000000002,l,r,1);
        }
        else{
            c=query(1,1000000002,l,r,1);
            cout<<c<<endl;
        }
    }



}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:74:11: warning: unused variable 'j' [-Wunused-variable]
   74 |     int i,j,t,l,r,m,c=0;
      |           ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 12 ms 3276 KB Output is correct
5 Correct 14 ms 4044 KB Output is correct
6 Correct 14 ms 3848 KB Output is correct
7 Correct 14 ms 4044 KB Output is correct
8 Correct 98 ms 29232 KB Output is correct
9 Correct 207 ms 50612 KB Output is correct
10 Correct 217 ms 55984 KB Output is correct
11 Correct 219 ms 60228 KB Output is correct
12 Correct 227 ms 62040 KB Output is correct
13 Correct 205 ms 72364 KB Output is correct
14 Correct 202 ms 72908 KB Output is correct
15 Correct 292 ms 133364 KB Output is correct
16 Correct 295 ms 134524 KB Output is correct
17 Correct 206 ms 75548 KB Output is correct
18 Correct 205 ms 75676 KB Output is correct
19 Correct 298 ms 137480 KB Output is correct
20 Correct 290 ms 137540 KB Output is correct