Submission #1257489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257489		dosts	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	411 ms	175792 KiB

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define alperen_t int32_t
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 998244353, inf = 1e18, LIM = 1e9;

const int N = 5e3+10;

struct Node {
    int id,lazy,sz,v;
};
int ctr = 0;
vector<Node> nds;
vi sol,sag;
int newnode(int x) {
    nds.push_back(Node{ctr++,0,x,0});
    sol.push_back(-1);
    sag.push_back(-1);
    return ctr-1;
}

void push(int node,int l,int r) {
    if (!nds[node].lazy) return;
    nds[node].v = nds[node].sz;
    if (l != r) {
        int m = (l+r) >> 1;
        if (sol[node] == -1) sol[node] = newnode(m-l+1);
        if (sag[node] == -1) sag[node] = newnode(r-m);
        nds[sol[node]].lazy = 1;
        nds[sag[node]].lazy = 1;
    }
    nds[node].lazy = 0;
}

int query(int node,int l,int r,int L,int R) {
    push(node,l,r);
    //cerr << "A" sp node sp nds[node].v sp nds[node].sz sp l sp r sp L sp R << endl;
    if (l >= L && r <= R) return nds[node].v;
    int m = (l+r) >> 1;
    int sm = 0;
    if (L <= m && sol[node] != -1) sm+=query(sol[node],l,m,L,R);
    if (m+1 <= R && sag[node] != -1) sm+=query(sag[node],m+1,r,L,R);
    return sm;
}

void update(int node,int l,int r,int L,int R) {
    push(node,l,r);
    //cerr << "U" sp node sp nds[node].v sp nds[node].sz sp l sp r sp L sp R << endl;
    if (l >= L && r <= R) {
        nds[node].lazy = 1;
        push(node,l,r);
        //cerr << "NW" sp node sp nds[node].v sp nds[node].sz sp l sp r sp L sp R << endl;
        return;
    }
    int m = (l+r) >> 1;
    if (L <= m) {
        if (sol[node] == -1) sol[node] = newnode(m-l+1);
        update(sol[node],l,m,L,R);
    }
    if (m+1 <= R) {
        if (sag[node] == -1) sag[node] = newnode(r-m);
        update(sag[node],m+1,r,L,R);
    }
    if (sol[node] != -1) push(sol[node],l,m);
    if (sag[node] != -1) push(sag[node],m+1,r);
    nds[node].v = 0;
    if (sol[node] != -1) nds[node].v+=nds[sol[node]].v;
    if (sag[node] != -1) nds[node].v+=nds[sag[node]].v;
}

void solve() {  
    int q;
    cin >> q;
    int c = 0;
    int root = newnode(LIM);
    while (q--) {
        int ty,l,r;
        cin >> ty >> l >> r;
        l+=c,r+=c;
        if (ty == 1) {
            c = query(root,1,LIM,l,r);
            cout << c << '\n';
        }
        else {
            update(root,1,LIM,l,r);
        }
    }
}   

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
    #ifdef Dodi 
        cerr << "TIME TAKEN: " << (double)clock()/(double)CLOCKS_PER_SEC << "seconds!\n";
    #endif
}

Compilation message (stderr)

apple.cpp:14:34: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const int MOD = 998244353, inf = 1e18, LIM = 1e9;
      |                                  ^~~~

• Subtask 1: 100 / 100