Submission #1116549

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1116549	2024-11-21T19:43:48 Z	Petrix	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	204 ms	97096 KB

apple

#include <iostream>
using namespace std;

#define int long long

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

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	504 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	7 ms	4688 KB	Output is correct
5	Correct	11 ms	6908 KB	Output is correct
6	Correct	8 ms	6736 KB	Output is correct
7	Correct	8 ms	6736 KB	Output is correct
8	Correct	72 ms	36680 KB	Output is correct
9	Runtime error	204 ms	97096 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-