Submission #709895

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
709895	2023-03-14T18:52:21 Z	liaoli	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	799 ms	262144 KB

apple

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define ff first
#define ss second

using namespace std;

typedef long long ftype;

const int MAX = 1e9+17;

struct Segtree {
    vector<ftype> seg, d, e, lazy;
    const ftype NEUTRAL = 0;
    const ftype NEUTRAL_LAZY = -1;
    int n;
    
    Segtree(int n) {
        this->n = n;
    }
    
    ftype apply_lazy(ftype a, ftype b, int len) {
        if (b == NEUTRAL_LAZY) return a;
        else return b * len;
    }
 
    void propagate(int pos, int ini, int fim) {
        if (seg[pos] == 0) return;
        
        if (ini == fim) {
            return;
        }
 
        int m = (ini + fim) >> 1;
        
        if (e[pos] == 0) e[pos] = create();
        if (d[pos] == 0) d[pos] = create();
 
        lazy[e[pos]] = apply_lazy(lazy[e[pos]], lazy[pos], 1);
        lazy[d[pos]] = apply_lazy(lazy[d[pos]], lazy[pos], 1);
 
        seg[e[pos]] = apply_lazy(seg[e[pos]], lazy[pos], m - ini + 1);
        seg[d[pos]] = apply_lazy(seg[d[pos]], lazy[pos], fim - m);
 
        lazy[pos] = NEUTRAL_LAZY;
    }
    
    ftype f(ftype a, ftype b) {
        return a + b;
    }

    ftype create() {
        seg.push_back(0);
        e.push_back(0);
        d.push_back(0);
        lazy.push_back(-1);
        return seg.size() - 1;
    }
    
    ftype query(int pos, int ini, int fim, int p, int q) {
        propagate(pos, ini, fim);
        if (q < ini || p > fim) return NEUTRAL;
        if (pos == 0) return 0;
        if (p <= ini && fim <= q) return seg[pos];
        int m = (ini + fim) >> 1;
        return f(query(e[pos], ini, m, p, q), query(d[pos], m + 1, fim, p, q));
    }
 
    void update(int pos, int ini, int fim, int p, int q, int val) {
        propagate(pos, ini, fim);
        if (ini > q || fim < p) {
            return;
        }
 
        if (ini >= p && fim <= q) {
            lazy[pos] = apply_lazy(lazy[pos], val, 1);
            seg[pos] = apply_lazy(seg[pos], val, fim - ini + 1);
 
            return;
        }
 
        int m = (ini + fim) >> 1;

        if (e[pos] == 0) e[pos] = create();
        update(e[pos], ini, m, p, q, val);

        if (d[pos] == 0) d[pos] = create();
        update(d[pos], m + 1, fim, p, q, val);
 
        seg[pos] = f(seg[e[pos]], seg[d[pos]]);
    }
 
    ftype query(int p, int q) {
        return query(1, 1, n, p, q);
    }
 
    void update(int p, int q, int val) {
        update(1, 1, n, p, q, val);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int q; cin >> q;
    Segtree seg = Segtree(MAX);
    int c = 0;
    
    seg.create();
    seg.create();
    
    while (q--) {
        int op; cin >> op;
        if (op == 1) {
            int x, y; cin >> x >> y;
            c = seg.query(x + c, y + c);
            cout << c << '\n';
        } else {
            int x, y; cin >> x >> y;
            seg.update(x + c, y + c, 1);
        }
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	27 ms	6104 KB	Output is correct
5	Correct	32 ms	7316 KB	Output is correct
6	Correct	32 ms	7116 KB	Output is correct
7	Correct	33 ms	7300 KB	Output is correct
8	Correct	241 ms	52456 KB	Output is correct
9	Correct	496 ms	89256 KB	Output is correct
10	Correct	541 ms	100036 KB	Output is correct
11	Correct	572 ms	108384 KB	Output is correct
12	Correct	575 ms	112176 KB	Output is correct
13	Correct	557 ms	167296 KB	Output is correct
14	Correct	587 ms	167412 KB	Output is correct
15	Correct	799 ms	254800 KB	Output is correct
16	Correct	764 ms	256704 KB	Output is correct
17	Correct	583 ms	167240 KB	Output is correct
18	Correct	586 ms	167456 KB	Output is correct
19	Correct	762 ms	262144 KB	Output is correct
20	Correct	757 ms	262144 KB	Output is correct