답안 #881735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881735	2023-12-01T19:54:59 Z	alexdd	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	2000 ms	30184 KB

apple

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
struct node
{
    int sum,lazy;
    int tole,tori;
};
vector<node> aint;
void propagate(int nod, int st, int dr)
{
    if(aint[nod].lazy==0)
        return;
    int le = aint[nod].tole;
    int ri = aint[nod].tori;
    int mij=(st+dr)/2;
    aint[le].sum = mij-st+1;
    aint[le].lazy = 1;
    aint[ri].sum = dr-mij;
    aint[ri].lazy = 1;
    aint[nod].lazy=0;
}
void upd(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return;
    if(st==dr)
    {
        aint[nod].sum = ri-le+1;
        return;
    }
    if(aint[nod].tole==-1)
    {
        aint[nod].tole=aint.size();
        aint.push_back({0,0,-1,-1});
    }
    if(aint[nod].tori==-1)
    {
        aint[nod].tori=aint.size();
        aint.push_back({0,0,-1,-1});
    }
    propagate(nod,st,dr);
    int mij=(st+dr)/2;
    upd(aint[nod].tole,st,mij,le,min(mij,ri));
    upd(aint[nod].tori,mij+1,dr,max(mij+1,le),ri);
    aint[nod].sum = aint[aint[nod].tole].sum + aint[aint[nod].tori].sum;
}
int qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return 0;
    if(le==st && dr==ri)
        return aint[nod].sum;
    if(aint[nod].tole==-1)
    {
        aint[nod].tole=aint.size();
        aint.push_back({0,0,-1,-1});
    }
    if(aint[nod].tori==-1)
    {
        aint[nod].tori=aint.size();
        aint.push_back({0,0,-1,-1});
    }
    propagate(nod,st,dr);
    int mij=(st+dr)/2;
    return qry(aint[nod].tole,st,mij,le,min(mij,ri)) +
           qry(aint[nod].tori,mij+1,dr,max(mij+1,le),ri);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    aint.reserve(40000000);
    int m,c=0,d,x,y;
    cin>>m;
    aint.push_back({0,0,-1,-1});
    while(m--)
    {
        cin>>d>>x>>y;
        x+=c;
        y+=c;
        if(d==1)
        {
            c = qry(0,1,INF,x,y);
            cout<<c<<"\n";
        }
        else
        {
            upd(0,1,INF,x,y);
        }
    }
    return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Execution timed out	2086 ms	30184 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-