oj.uz

Submission #1098671

# Submission time Handle Problem Language Result Execution time Memory
1098671 2024-10-09T16:41:24 Z AHOKA Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
 196 ms 149136 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 = 1e5 + 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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 3672 KB Output is correct
5 Correct 9 ms 4188 KB Output is correct
6 Correct 10 ms 4184 KB Output is correct
7 Correct 10 ms 4184 KB Output is correct
8 Correct 64 ms 30292 KB Output is correct
9 Correct 159 ms 52524 KB Output is correct
10 Correct 153 ms 57776 KB Output is correct
11 Correct 156 ms 62036 KB Output is correct
12 Correct 155 ms 63852 KB Output is correct
13 Correct 140 ms 74324 KB Output is correct
14 Runtime error 196 ms 149136 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -