답안 #381264

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381264 2021-03-25T00:21:44 Z ScarletS 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
382 ms 108692 KB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct implicit
{
    struct node
    {
        node *l,*r;
        int val = 0;
        bool allSet = 0;
    };
    deque<node> buffer;
    int n;
    node *root;
    node *newnode()
    {
        buffer.emplace_back();
        return &buffer.back();
    }
    implicit(int n) : n(n) {root=newnode();}
    void passDown(node *&v)
    {
        if (!(v->l))
            v->l=newnode();
        if (!(v->r))
            v->r=newnode();
        if (v->allSet)
        {
            v->l->allSet=1;
            v->r->allSet=1;
        }
    }
    int calc(node *&v, int l, int r)
    {
        if (v->allSet)
            return r-l+1;
        return v->val;
    }
    void update(node *&v, int cL, int cR, int l, int r)
    {
        if (r<cL||cR<l)
            return;
        if (l<=cL&&cR<=r)
        {
            v->allSet=1;
            return;
        }
        passDown(v);
        update(v->l,cL,cL+(cR-cL)/2,l,r);
        update(v->r,cL+(cR-cL)/2+1,cR,l,r);
        v->val=calc(v->l,cL,cL+(cR-cL)/2)+calc(v->r,cL+(cR-cL)/2+1,cR);
    }
    void update(int l, int r)
    {
        update(root,1,n,l,r);
    }
    int query(node *&v, int cL, int cR, int l, int r)
    {
        if (r<cL||cR<l)
            return 0;
        if (l<=cL&&cR<=r)
            return calc(v,cL,cR);
        passDown(v);
        int rtn = query(v->l,cL,cL+(cR-cL)/2,l,r) + query(v->r,cL+(cR-cL)/2+1,cR,l,r);
        v->val=calc(v->l,cL,cL+(cR-cL)/2)+calc(v->r,cL+(cR-cL)/2+1,cR);
        return rtn;
    }
    int query(int l, int r)
    {
        return query(root,1,n,l,r);
    }
};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,d,x,y,c=0;
    cin>>n;
    implicit seg(1e9);
    while (n--)
    {
        cin>>d>>x>>y;
        if (d==1)
        {
            c=seg.query(x+c,y+c);
            cout<<c<<"\n";
        }
        else
            seg.update(x+c,y+c);
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 17 ms 2796 KB Output is correct
5 Correct 18 ms 3436 KB Output is correct
6 Correct 18 ms 3320 KB Output is correct
7 Correct 17 ms 3436 KB Output is correct
8 Correct 117 ms 23712 KB Output is correct
9 Correct 248 ms 41176 KB Output is correct
10 Correct 262 ms 45272 KB Output is correct
11 Correct 272 ms 48612 KB Output is correct
12 Correct 273 ms 50240 KB Output is correct
13 Correct 273 ms 58404 KB Output is correct
14 Correct 255 ms 59376 KB Output is correct
15 Correct 381 ms 105748 KB Output is correct
16 Correct 382 ms 106356 KB Output is correct
17 Correct 264 ms 60832 KB Output is correct
18 Correct 252 ms 60752 KB Output is correct
19 Correct 369 ms 108692 KB Output is correct
20 Correct 373 ms 108692 KB Output is correct