Submission #783644

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
783644	2023-07-15T07:16:51 Z	ezraft	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	530 ms	195920 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	19 ms	4544 KB	Output is correct
5	Correct	22 ms	5380 KB	Output is correct
6	Correct	22 ms	5188 KB	Output is correct
7	Correct	22 ms	5460 KB	Output is correct
8	Correct	144 ms	39468 KB	Output is correct
9	Correct	306 ms	71544 KB	Output is correct
10	Correct	299 ms	75368 KB	Output is correct
11	Correct	328 ms	81564 KB	Output is correct
12	Correct	326 ms	84100 KB	Output is correct
13	Correct	328 ms	104112 KB	Output is correct
14	Correct	318 ms	105048 KB	Output is correct
15	Correct	455 ms	189772 KB	Output is correct
16	Correct	530 ms	191236 KB	Output is correct
17	Correct	351 ms	108748 KB	Output is correct
18	Correct	322 ms	108724 KB	Output is correct
19	Correct	462 ms	195916 KB	Output is correct
20	Correct	481 ms	195920 KB	Output is correct