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

apple

#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;
      |           ^

Subtask #1

100.0 / 100.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