Submission #1098753

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098753	2024-10-09T20:31:04 Z	Ardelion	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	222 ms	139604 KB

apple

#include <bits/stdc++.h>

using namespace std;

#define int          long long
#define ll           long long
#define X            first
#define Y            second
#define pb           push_back
#define lb           lower_bound
#define ub           upper_bound
#define mp           make_pair
#define sep          ' '
#define endl         "\n"
#define migmig       ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FileIO       freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(x)       x.begin(), x.end()
#define ret(x)       {cout << x << endl; return;}
#define md(x)        ((x%MOD+MOD)%MOD)

typedef pair<int, int> pii;
typedef pair<ll , ll > pll;

const int N     = 2e5+13;
const int LOG   = 64;
const int MOD   = 1e9 + 7; //998244353; //1e9+9;
const int INF   = 1e9 + 6; //1e18;
const int dx[4] = {1, -1, 0,  0};
const int dy[4] = {0,  0, 1, -1};

ll GCD(ll _a, ll _b) { return (!_b ? _a : GCD(_b, _a % _b)); }
ll POW(ll _a, ll _b) { return !_b ? 1 : ((_b & 1 ? _a : 1) * POW(_a * _a % MOD, _b / 2)) % MOD;}

int q, c, cnt=1;
int seg[LOG*N], lazy[LOG*N], lc[LOG*N], rc[LOG*N];

void G(int id, int l, int r, int val) {
    lazy[id] |= val;
    seg[id] = max(seg[id], (r-l) * val);
}

void PUSH(int id, int l, int r) {
    if(!lc[id]) {
        lc[id] = ++cnt;
        rc[id] = ++cnt;
    }
    int mid = (l+r)/2;
    G(lc[id], l, mid, lazy[id]);
    G(rc[id], mid, r, lazy[id]);
    lazy[id] = 0;
}

void UPD(int id, int l, int r, int ql, int qr) {
    if(r <= ql || qr <= l) {
        return;
    }
    if(ql <= l && r <= qr) {
        G(id, l, r, 1);
        return;
    }
    PUSH(id, l, r);
    int mid = (l+r)/2;
    UPD(lc[id], l, mid, ql, qr);
    UPD(rc[id], mid, r, ql, qr);
    seg[id] = seg[lc[id]] + seg[rc[id]];
}

int GET(int id, int l, int r, int ql, int qr) {
    if(r <= ql || qr <= l) {
        return 0;
    }
    if(ql <= l && r <= qr) {
        return seg[id];
    }
    PUSH(id, l, r);
    int mid = (l+r)/2;
    return GET(lc[id], l, mid, ql, qr) + GET(rc[id], mid, r, ql, qr);
}

void F() {
    cin >> q;
    int cmd, ql, qr;
    while(q--) {
        cin >> cmd >> ql >> qr;
        ql += c;
        qr += c + 1;
        if(cmd == 1) {
            c = GET(1, 0, INF, ql, qr);
            cout << c << endl;
        }
        if(cmd == 2) {
            UPD(1, 0, INF, ql, qr);
        }
    }
}

int32_t main() {
    migmig;
    //PREP();
    int t=1;
    //cin >> t;
    while(t--)
        F();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	8 ms	3620 KB	Output is correct
5	Correct	9 ms	4188 KB	Output is correct
6	Correct	10 ms	4056 KB	Output is correct
7	Correct	9 ms	4188 KB	Output is correct
8	Correct	67 ms	30288 KB	Output is correct
9	Correct	141 ms	52304 KB	Output is correct
10	Correct	160 ms	57848 KB	Output is correct
11	Correct	148 ms	62032 KB	Output is correct
12	Correct	145 ms	63828 KB	Output is correct
13	Correct	139 ms	74324 KB	Output is correct
14	Correct	135 ms	75148 KB	Output is correct
15	Correct	195 ms	135508 KB	Output is correct
16	Correct	201 ms	136648 KB	Output is correct
17	Correct	148 ms	77396 KB	Output is correct
18	Correct	152 ms	77756 KB	Output is correct
19	Correct	222 ms	139600 KB	Output is correct
20	Correct	210 ms	139604 KB	Output is correct