제출 #783644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
783644		ezraft	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	530 ms	195920 KiB

apple

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1 << 30;

struct Node 
{
    int t, d;
    Node* ch[2];
};

Node* make()
{
    Node* v = new Node();
    
    v->t = v->d = 0;
    
    for (int i = 0; i < 2; i++)
    {
        v->ch[i] = NULL;
    }
    
    return v;
}

struct Seg 
{
    int n;
    Node* rt;
    
    Seg (int _n)
    {
        n = _n;
        rt = make();
    }
    
    void apply (Node* p, bool v, int sz)
    {
        if (v)
        {
            p->d = 1;
            p->t = sz;
        }
    }
    
    void pull (Node* p, int sz)
    {
        p->t = p->d?sz : p->ch[0]->t + p->ch[1]->t;
    }
    
    void push (Node* p, int cl, int cm, int cr)
    {
        if (cl == cr)
        {
            return;
        }
        
        for (int i = 0; i < 2; i++)
        {
            if (p->ch[i] == NULL)
            {
                p->ch[i] = make();
            }
        }
        
        apply(p->ch[0], p->d, cm - cl + 1);
        apply(p->ch[1], p->d, cr - cm);
        p->d = 0;
    }
    
    void upd (int l, int r, int cl, int cr, Node* p)
    {
        if (cr < l || cl > r)
        {
            return;
        }
        int cm = (cl + cr)/2;
        
        push(p, cl, cm, cr);
        
        if (l <= cl && cr <= r)
        {
            apply(p, 1, cr - cl + 1);
            return;
        }
        
        upd(l, r, cl, cm, p->ch[0]);
        upd(l, r, cm + 1, cr, p->ch[1]);
        pull(p, cr - cl + 1);
    }
    
    void upd (int l, int r)
    {
        upd(l,r,0,MAXN-1,rt);
    }
    
    int query (int l, int r, int cl, int cr, Node* p)
    {
        if (cr < l || cl > r)
        {
            return 0;
        }
        
        int cm = (cl + cr)/2;
        
        push(p, cl, cm, cr);
        
        if (l <= cl && cr <= r)
        {
            return p->t;
        }
        
        int sz = min(cr, r) - max(cl, l) + 1;
        return p->d? sz : query(l,r,cl,cm, p->ch[0]) + query(l,r,cm + 1, cr, p->ch[1]);
    }
    
    int query (int l, int r)
    {
        return query(l,r,0,MAXN-1,rt);
    }
        
};


int main()
{
    //~ ifstream cin("f.in");
    //~ ofstream cout("f.out");
    int n;
    cin >> n;
    int c = 0;
    Seg t(MAXN);
    
    for (int i = 0; i < n; i++)
    {
        int ty;
        cin >> ty;
        if (ty == 2)
        {
            int l, r;
            cin >> l >> r;
            l--,r--;
            l += c, r += c;
            t.upd(l,r);
        } else
        {
            int l, r;
            cin >> l >> r;
            l--,r--;
            l += c, r += c;
            int z = t.query(l,r);
            cout << z << "\n";
            c = z;
        }
    }
 return 0;
}

• Subtask 1: 100 / 100