oj.uz

Submission #1098673

# Submission time Handle Problem Language Result Execution time Memory
1098673 2024-10-09T16:42:50 Z AHOKA Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 213 ms 139448 KB 
#pragma GCC optimize("O3") 

#include <bits/stdc++.h>

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 4e5 + 10, maxm = 2e2 + 10, oo = 4e8 + 10, lg = 23, sq = 700, mod = 1e9 + 7;

int m, cnt = 1, c;

int seg[maxn * lg], lazy[maxn * lg];
int lc[maxn * lg], rc[maxn * lg];

void merge(int id){
    seg[id] = seg[lc[id]] + seg[rc[id]];
}
 
void add(int id, int l, int r, int v){
    lazy[id] |= v;
    seg[id] = max(seg[id], (r - l) * v);
}

void relax(int id, int l, int r){
    if(!lc[id]){
        lc[id] = ++cnt;
        rc[id] = ++cnt;
    }

    int mid = (l + r) / 2;
 
    add(lc[id], l, mid, lazy[id]);
    add(rc[id], mid, r, lazy[id]);
    
    lazy[id] = 0;
}
 
void upd(int ql, int qr, int v, int id = 1, int l = 0, int r = mod){
    if(r <= ql || qr <= l)
        return;
    if(ql <= l && r <= qr){
        add(id, l, r, v);
        return;
    }
 
    relax(id, l, r);
 
    int mid = (l + r) / 2;
    upd(ql, qr, v, lc[id], l, mid);
    upd(ql, qr, v, rc[id], mid, r);
 
    merge(id);
}
 
int get(int ql, int qr, int id = 1, int l = 0, int r = mod){
    if(r <= ql || qr <= l)
        return 0;
 
    if(ql <= l && r <= qr)
        return seg[id];
 
    relax(id, l, r);
 
    int mid = (l + r) / 2;
 
    return get(ql, qr, lc[id], l, mid) + get(ql, qr, rc[id], mid, r);
}
 
signed main()
{
    threesum;
    cin >> m;
 
    while (m--)
    {
        int t, l, r;
        cin >> t >> l >> r;

        l += c;
        r += c + 1;

        if (t == 2)
            upd(l, r, 1);
        else
        {
            int x = get(l, r);
            cout << x << "\n";
            c = x;
        }
    }
}
/*
5
1 0 3 3
2 1
1 2 4 4
2 3
2 4

*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 7 ms 3544 KB Output is correct
5 Correct 8 ms 4096 KB Output is correct
6 Correct 11 ms 3932 KB Output is correct
7 Correct 9 ms 4176 KB Output is correct
8 Correct 64 ms 29340 KB Output is correct
9 Correct 132 ms 50772 KB Output is correct
10 Correct 132 ms 55904 KB Output is correct
11 Correct 139 ms 60184 KB Output is correct
12 Correct 141 ms 62148 KB Output is correct
13 Correct 125 ms 72340 KB Output is correct
14 Correct 130 ms 73036 KB Output is correct
15 Correct 195 ms 135608 KB Output is correct
16 Correct 206 ms 136548 KB Output is correct
17 Correct 129 ms 77616 KB Output is correct
18 Correct 146 ms 77648 KB Output is correct
19 Correct 208 ms 139448 KB Output is correct
20 Correct 213 ms 139432 KB Output is correct