답안 #984503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
984503	2024-05-16T17:52:30 Z	ivaziva	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	2000 ms	262144 KB

apple

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100010

struct Segmentno{
    long long levodete=-1;
    long long desnodete=-1;
    long long levagranica;
    long long desnagranica;
    long long suma=0;
    long long lazy=0;
};

long long m;
Segmentno seg[30*MAXN];
long long cnt=2;

void push(long long node)
{
    if (seg[node].lazy==0) return;
    seg[node].suma=seg[node].desnagranica-seg[node].levagranica+1;
    long long mid=(seg[node].levagranica+seg[node].desnagranica)/2;
    if (seg[node].levodete==-1)
    {
        seg[node].levodete=cnt;cnt++;
        seg[seg[node].levodete].levagranica=seg[node].levagranica;
        seg[seg[node].levodete].desnagranica=mid;
    }
    if (seg[node].desnodete==-1)
    {
        seg[node].desnodete=cnt;cnt++;
        seg[seg[node].desnodete].levagranica=mid+1;
        seg[seg[node].desnodete].desnagranica=seg[node].desnagranica;
    }
    seg[seg[node].levodete].lazy=1;
    seg[seg[node].desnodete].lazy=1;
    seg[node].lazy=0;
}

void update(long long node,long long l,long long r)
{
    push(node);
    if (l==seg[node].levagranica and r==seg[node].desnagranica) {seg[node].lazy=1;push(node);}
    else
    {
        long long mid=(seg[node].levagranica+seg[node].desnagranica)/2;
        if (seg[node].levodete==-1)
        {
            seg[node].levodete=cnt;cnt++;
            seg[seg[node].levodete].levagranica=seg[node].levagranica;
            seg[seg[node].levodete].desnagranica=mid;
        }
        if (seg[node].desnodete==-1)
        {
            seg[node].desnodete=cnt;cnt++;
            seg[seg[node].desnodete].levagranica=mid+1;
            seg[seg[node].desnodete].desnagranica=seg[node].desnagranica;
        }
        if (l>mid) update(seg[node].desnodete,l,r);
        else if (r<=mid) update(seg[node].levodete,l,r);
        else
        {
            update(seg[node].levodete,l,mid);
            update(seg[node].desnodete,mid+1,r);
        }
        push(seg[node].levodete);
        push(seg[node].desnodete);
        seg[node].suma=seg[seg[node].levodete].suma+seg[seg[node].desnodete].suma;
    }
}

long long query(long long node,long long l,long long r)
{
    push(node);
    if (l==seg[node].levagranica and r==seg[node].desnagranica) return seg[node].suma;
    long long mid=(seg[node].levagranica+seg[node].desnagranica)/2;
    if (seg[node].levodete==-1)
    {
        seg[node].levodete=cnt;cnt++;
        seg[seg[node].levodete].levagranica=seg[node].levagranica;
        seg[seg[node].levodete].desnagranica=mid;
    }
    if (seg[node].desnodete==-1)
    {
        seg[node].desnodete=cnt;cnt++;
        seg[seg[node].desnodete].levagranica=mid+1;
        seg[seg[node].desnodete].desnagranica=seg[node].desnagranica;
    }
    if (l>mid) return query(seg[node].desnodete,l,r);
    else if (r<=mid) return query(seg[node].levodete,l,r);
    else return query(seg[node].levodete,l,mid)+query(seg[node].desnodete,mid+1,r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>m;
    seg[1].levagranica=1;
    seg[1].desnagranica=1000000000;
    seg[1].suma=0,seg[1].lazy=0;
    long long ans=0;
    for (long long z=0;z<m;z++)
    {
        long long t;cin>>t;
        if (t==1)
        {
            long long x,y;cin>>x>>y;
            ans=query(1,x+ans,y+ans);
            cout<<ans<<endl;
        }
        else
        {
            long long x,y;cin>>x>>y;
            update(1,x+ans,y+ans);
        }
    }
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	141260 KB	Output is correct
2	Correct	36 ms	141292 KB	Output is correct
3	Correct	36 ms	141136 KB	Output is correct
4	Correct	48 ms	141136 KB	Output is correct
5	Correct	52 ms	141400 KB	Output is correct
6	Correct	51 ms	141360 KB	Output is correct
7	Correct	52 ms	141140 KB	Output is correct
8	Correct	157 ms	141392 KB	Output is correct
9	Correct	289 ms	141644 KB	Output is correct
10	Execution timed out	2297 ms	262144 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-