Submission #795943

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
795943	2023-07-27T23:35:34 Z	idiotcomputer	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	389 ms	235584 KB

apple

#include <bits/stdc++.h>
using namespace std;

struct node {
    int sum = 0;
    int l = -1;
    int r = -1;
    int tl,tr;
    bool has = false;
};

const int MAX_N = 2500000;
const int MAX_V = 1e9;

int cnt = 0;
node segt[4*MAX_N+1];

void timeout(){
    if (cnt >= 4*MAX_N+1){
        while (true){
            cnt += 1;
        }
    }    
}

void upd(int idx, int tl, int tr){
    if (segt[idx].tl > tr || segt[idx].tr < tl){
        return;
    }
    if (segt[idx].tl >= tl && segt[idx].tr <= tr){
        segt[idx].has = true;
        segt[idx].sum = segt[idx].tr - segt[idx].tl + 1;
        return;
    }
    int mid = (segt[idx].tl + segt[idx].tr)/2;
    if (segt[idx].l == -1){
        segt[idx].l = cnt;
        cnt ++;
        timeout();
        segt[segt[idx].l].tl = segt[idx].tl;
        segt[segt[idx].l].tr = mid;
    }
    if (segt[idx].r == -1){
        segt[idx].r = cnt;
        cnt ++;
        timeout();
        segt[segt[idx].r].tl = mid+1;
        segt[segt[idx].r].tr = segt[idx].tr;
    }
    upd(segt[idx].l,tl,tr);
    upd(segt[idx].r,tl,tr);

    //setting sum
    int cl = segt[idx].l;
    int cr = segt[idx].r;
    if (segt[idx].has){
        segt[idx].sum = segt[idx].tr - segt[idx].tl +1;
        return;
    }
    segt[idx].sum = segt[cl].sum + segt[cr].sum;
    return;
}

int query(int idx, int tl, int tr, bool chas){
    if (segt[idx].tl > tr || segt[idx].tr < tl){
        return 0;
    }
    if (segt[idx].has){
        chas = true;
    }
    if (segt[idx].tl >= tl && segt[idx].tr <= tr){
   //     cout << idx << ": " << segt[idx].tl << ' ' << segt[idx].tr <<" " << segt[idx].sum << " asd " << tl << ", " << tr << " " << (int) chas << '\n';
        if (chas){
            return segt[idx].tr - segt[idx].tl + 1;
        }
        return segt[idx].sum;
    }
    int mid = (segt[idx].tr + segt[idx].tl)/2;
    if (segt[idx].l == -1){
        segt[idx].l = cnt;
        cnt ++;
        timeout();
        segt[segt[idx].l].tl = segt[idx].tl;
        segt[segt[idx].l].tr = mid;
    }
    if (segt[idx].r == -1){
        segt[idx].r = cnt;
        cnt ++;
        timeout();
        segt[segt[idx].r].tl = mid+1;
        segt[segt[idx].r].tr = segt[idx].tr;
    }
        
    return query(segt[idx].l,tl,tr,chas)+query(segt[idx].r,tl,tr,chas);
    
}

int main()
{
    int m;
    cin >> m;
    
    int d,x,y;
    segt[0].tl = 1;
    segt[0].tr = MAX_V;
 //   cout << segt[1].tl << ' ' << segt[1].tr << " " << segt[1].sum << " " << segt[1].l << " " << segt[1].r << " " << segt[1].has<<'\n';
    cnt ++;
    int c = 0;
    int res;
 
    for (int i =0; i < m; i++){
        cin >> d >> x >> y;
        if (d == 1){
      //      cout << c << ": ";
            res = query(0,x+c,y+c,false);
            c = res;
            cout << res << '\n';
        } else {
            upd(0,x+c,y+c);
        }
    }
    
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	235056 KB	Output is correct
2	Correct	91 ms	235072 KB	Output is correct
3	Correct	89 ms	235056 KB	Output is correct
4	Correct	109 ms	235072 KB	Output is correct
5	Correct	108 ms	235048 KB	Output is correct
6	Correct	115 ms	235048 KB	Output is correct
7	Correct	111 ms	235084 KB	Output is correct
8	Correct	206 ms	235468 KB	Output is correct
9	Correct	328 ms	235388 KB	Output is correct
10	Correct	365 ms	235480 KB	Output is correct
11	Correct	330 ms	235468 KB	Output is correct
12	Correct	328 ms	235380 KB	Output is correct
13	Correct	315 ms	235540 KB	Output is correct
14	Correct	306 ms	235504 KB	Output is correct
15	Correct	372 ms	235572 KB	Output is correct
16	Correct	368 ms	235504 KB	Output is correct
17	Correct	336 ms	235560 KB	Output is correct
18	Correct	309 ms	235584 KB	Output is correct
19	Correct	363 ms	235516 KB	Output is correct
20	Correct	389 ms	235544 KB	Output is correct