Submission #1098673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098673		AHOKA	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	213 ms	139448 KiB

apple

#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 / 100