Submission #1116550

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1116550	2024-11-21T19:45:16 Z	Petrix	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	188 ms	88392 KB

apple

#include <iostream>
using namespace std;


int cnt;
struct node{
    int sum,mar,lazy,lnod,rnod;
} v[6000000];

void push(int nod){
    int st=v[nod].lnod,dr=v[nod].rnod;
    if(v[nod].lazy){
        v[nod].lazy=0;
        v[st].lazy=v[dr].lazy=1;
        v[st].sum=v[st].mar;
        v[dr].sum=v[dr].mar;
    }
}

void update(int nod,int st,int dr,int l,int r){
    if(l<=st && dr<=r){
        v[nod].sum=v[nod].mar;
        v[nod].lazy=1;
        return;
    }
    int mij=(st+dr)/2;
    if(v[nod].lnod==0){
        cnt++;
        v[nod].lnod=cnt;
        v[v[nod].lnod]={0,mij-st+1,0,0,0};
    }
    if(v[nod].rnod==0){
        cnt++;
        v[nod].rnod=cnt;
        v[v[nod].rnod]={0,dr-mij,0,0,0};
    }
    int st1=v[nod].lnod,dr1=v[nod].rnod;
    push(nod);
    if(l<=mij) update(st1,st,mij,l,r);
    if(mij+1<=r) update(dr1,mij+1,dr,l,r);
    v[nod].sum=v[st1].sum+v[dr1].sum;
}

int query(int nod,int st,int dr,int l,int r){
    if(l<=st && dr<=r) return v[nod].sum;
    int mij=(st+dr)/2;
    if(v[nod].lnod==0){
        cnt++;
        v[nod].lnod=cnt;
        v[v[nod].lnod]={0,mij-st+1,0,0,0};
    }
    if(v[nod].rnod==0){
        cnt++;
        v[nod].rnod=cnt;
        v[v[nod].rnod]={0,dr-mij,0,0,0};
    }
    int st1=v[nod].lnod,dr1=v[nod].rnod,rasp=0;
    push(nod);
    if(l<=mij) rasp+=query(st1,st,mij,l,r);
    if(mij+1<=r) rasp+=query(dr1,mij+1,dr,l,r);
    return rasp;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,i,cer,aux=0,a,b,rasp;
    cin>>n;
    cnt=1;
    v[1]={0,n,0,0,0};
    for(i=1;i<=n;i++){
        cin>>cer>>a>>b;
        if(cer==1){
            rasp=query(1,1,1e9,a+aux,b+aux);
            cout<<rasp<<"\n";
            aux=rasp;
        }else{
            update(1,1,1e9,a+aux,b+aux);
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	6 ms	2640 KB	Output is correct
5	Correct	8 ms	4688 KB	Output is correct
6	Correct	8 ms	2808 KB	Output is correct
7	Correct	7 ms	4688 KB	Output is correct
8	Correct	43 ms	18512 KB	Output is correct
9	Correct	122 ms	31824 KB	Output is correct
10	Correct	108 ms	36424 KB	Output is correct
11	Correct	116 ms	38984 KB	Output is correct
12	Correct	126 ms	40016 KB	Output is correct
13	Correct	113 ms	46664 KB	Output is correct
14	Correct	132 ms	47180 KB	Output is correct
15	Correct	174 ms	85736 KB	Output is correct
16	Correct	183 ms	86340 KB	Output is correct
17	Correct	115 ms	49480 KB	Output is correct
18	Correct	131 ms	49736 KB	Output is correct
19	Correct	188 ms	88392 KB	Output is correct
20	Correct	182 ms	88392 KB	Output is correct