Submission #1116545

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1116545	2024-11-21T19:42:41 Z	Petrix	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	819 ms	262144 KB

apple

#include <iostream>
using namespace std;

#define int long long

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

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

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	4776 KB	Output is correct
5	Correct	8 ms	6736 KB	Output is correct
6	Correct	8 ms	6736 KB	Output is correct
7	Correct	8 ms	6736 KB	Output is correct
8	Correct	61 ms	36436 KB	Output is correct
9	Correct	144 ms	64840 KB	Output is correct
10	Correct	139 ms	71712 KB	Output is correct
11	Correct	152 ms	76872 KB	Output is correct
12	Correct	185 ms	79176 KB	Output is correct
13	Correct	166 ms	92232 KB	Output is correct
14	Correct	157 ms	93092 KB	Output is correct
15	Runtime error	819 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-