Submission #1086078

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1086078	2024-09-09T13:19:49 Z	AliHasanli	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	383 ms	139604 KB

apple

#include<bits/stdc++.h>
using namespace std;
struct node
{
    node* left;
    node* right;
    long long val;
    node()
    {
        left=NULL;
        right=NULL;
        val=0;
    }
    void c()
    {
        if(left==NULL)left=new node();
        if(right==NULL)right=new node();
    }
};
node* root=new node();
//node* lazy=new node();
void update(node* root,long long l,long long r,long long ql,long long qr)
{
    if(l>r || ql>qr || ql>r || l>qr)return;
    if(ql<=l && r<=qr){root->val=(r-l+1);return;}
    root->c();
    if(root->val==r-l+1)root->left->val=((l+r)/2-l+1),root->right->val=(r-(l+r)/2);
    update(root->left,l,(l+r)/2,ql,qr),update(root->right,(l+r)/2+1,r,ql,qr);
    root->val=(root->left->val)+(root->right->val);
}
long long query(node* root,long long l,long long r,long long ql,long long qr)
{
    //cout<<"A "<<l<<" "<<r<<endl;
    if(l>r || ql>qr || ql>r || l>qr)return 0;
    if(ql<=l && r<=qr)return root->val;
    root->c();
    if(root->val==r-l+1)root->left->val=((l+r)/2-l+1),root->right->val=(r-(l+r)/2);
    return query(root->left,l,(l+r)/2,ql,qr)+query(root->right,(l+r)/2+1,r,ql,qr);
}
int main()
{
    //freopen("f.in","r",stdin);
    //freopen("f.out","w",stdout);
    int m;
    cin>>m;
    long long c=0;
    while(m--)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            long long l,r;
            cin>>l>>r;
            l--;r--;
            cout<<query(root,0,999999999,l+c,r+c)<<endl;
            c=query(root,0,999999999,l+c,r+c);
        }
        else
        {
            long long l,r;
            cin>>l>>r;
            l--;r--;
            update(root,0,999999999,l+c,r+c);
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	16 ms	3420 KB	Output is correct
5	Correct	20 ms	4180 KB	Output is correct
6	Correct	20 ms	4184 KB	Output is correct
7	Correct	21 ms	4188 KB	Output is correct
8	Correct	131 ms	30108 KB	Output is correct
9	Correct	259 ms	52304 KB	Output is correct
10	Correct	266 ms	57784 KB	Output is correct
11	Correct	274 ms	62032 KB	Output is correct
12	Correct	271 ms	63828 KB	Output is correct
13	Correct	267 ms	74324 KB	Output is correct
14	Correct	269 ms	74924 KB	Output is correct
15	Correct	379 ms	135504 KB	Output is correct
16	Correct	362 ms	136364 KB	Output is correct
17	Correct	265 ms	77396 KB	Output is correct
18	Correct	290 ms	77668 KB	Output is correct
19	Correct	363 ms	139440 KB	Output is correct
20	Correct	383 ms	139604 KB	Output is correct