Submission #1116547

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

apple

#include <iostream>
using namespace std;

#define int long long

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

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	7 ms	4756 KB	Output is correct
5	Correct	9 ms	6800 KB	Output is correct
6	Correct	8 ms	6736 KB	Output is correct
7	Correct	8 ms	6736 KB	Output is correct
8	Runtime error	104 ms	64248 KB	Execution killed with signal 11
9	Halted	0 ms	0 KB	-