Submission #967819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
967819	2024-04-23T00:36:46 Z	irmuun	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	262144 KB

apple

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=6e6;

struct Node{
    int sum,lazy,tl,tr,l,r;
    Node() : sum(0), lazy(0), l(-1), r(-1){}
};

Node sg[N];

int cnt=2;

void push(int node){
    if(sg[node].lazy==1){
        sg[node].sum=sg[node].tr-sg[node].tl+1;
        int mid=(sg[node].tl+sg[node].tr)/2;
        if(sg[node].l==-1){
            sg[node].l=cnt++;
            sg[sg[node].l].tl=sg[node].tl;
            sg[sg[node].l].tr=mid;
        }
        if(sg[node].r==-1){
            sg[node].r=cnt++;
            sg[sg[node].r].tl=mid+1;
            sg[sg[node].r].tr=sg[node].tr;
        }
        sg[sg[node].l].lazy=1;
        sg[sg[node].r].lazy=1;
        sg[node].lazy=0;
    }
}

int query(int node,int l,int r){
    push(node);
    if(sg[node].tl==l&&sg[node].tr==r){
        return sg[node].sum;
    }
    int mid=(sg[node].tl+sg[node].tr)/2;
    if(sg[node].l==-1){
        sg[node].l=cnt++;
        sg[sg[node].l].tl=sg[node].tl;
        sg[sg[node].l].tr=mid;
    }
    if(sg[node].r==-1){
        sg[node].r=cnt++;
        sg[sg[node].r].tl=mid+1;
        sg[sg[node].r].tr=sg[node].tr;
    }
    if(r<=mid){
        return query(sg[node].l,l,r);
    }
    if(l>mid){
        return query(sg[node].r,l,r);
    }
    return query(sg[node].l,l,mid)+query(sg[node].r,mid+1,r);
}

void update(int node,int l,int r){
    push(node);
    if(sg[node].tl==l&&sg[node].tr==r){
        sg[node].lazy=1;
        push(node);
        return;
    }
    int mid=(sg[node].tl+sg[node].tr)/2;
    if(sg[node].l==-1){
        sg[node].l=cnt++;
        sg[sg[node].l].tl=sg[node].tl;
        sg[sg[node].l].tr=mid;
    }
    if(sg[node].r==-1){
        sg[node].r=cnt++;
        sg[sg[node].r].tl=mid+1;
        sg[sg[node].r].tr=sg[node].tr;
    }
    if(r<=mid){
        update(sg[node].l,l,r);
    }
    else if(l>mid){
        update(sg[node].r,l,r);
    }
    else{
        update(sg[node].l,l,mid);
        update(sg[node].r,mid+1,r);
    }
    push(sg[node].l);
    push(sg[node].r);
    sg[node].sum=sg[sg[node].l].sum+sg[sg[node].r].sum;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int m;
    cin>>m;
    sg[1].sum=0;
    sg[1].lazy=0;
    sg[1].tl=1;
    sg[1].tr=1e9;
    int c=0;
    while(m--){
        int t,x,y;
        cin>>t>>x>>y;
        if(t==1){
            c=query(1,x+c,y+c);
            cout<<c<<"\n";
        }
        else{
            update(1,x+c,y+c);
        }
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	141140 KB	Output is correct
2	Correct	25 ms	141148 KB	Output is correct
3	Correct	25 ms	141140 KB	Output is correct
4	Correct	33 ms	141652 KB	Output is correct
5	Correct	33 ms	141384 KB	Output is correct
6	Correct	33 ms	141404 KB	Output is correct
7	Correct	38 ms	141316 KB	Output is correct
8	Correct	93 ms	142156 KB	Output is correct
9	Correct	188 ms	143440 KB	Output is correct
10	Correct	194 ms	143432 KB	Output is correct
11	Correct	202 ms	143452 KB	Output is correct
12	Correct	215 ms	143680 KB	Output is correct
13	Correct	174 ms	143700 KB	Output is correct
14	Correct	166 ms	143700 KB	Output is correct
15	Execution timed out	2476 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-