Submission #1098699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098699		MPG	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	575 ms	262144 KiB

apple

#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("O1, O2, O3, Ofast")
#pragma GCC optimization ("trapv")
#pragma GCC optimization ("sse, sse2, sse3, sse4, sse4.1, sse4.2, avx")



#include <bits/stdc++.h>
using namespace std;
typedef long long                           ll;
#define                                     max_heap priority_queue<ll>
#define                                     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>> // size(), push(), top(), pop();
//#define                                     min_heap priority_queue<ll, vector<ll>, greater<ll>>
#define                                     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define                                     filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout);
#define                                     endl '\n'
#define                                     md(a) (a % mod + mod) % mod
//cout << setprecision(5) << f;
ll const maxn = 2e5 + 10;
ll const inf = 2e18;
ll const loG = 23;
ll const mod = 998244353; //1e9 + 9, // 1e9 + 7;
ll const sq = 750;
ll power(ll a, ll b, ll mod){if (b == 0) return 1; if (b == 1) return a; ll x = power(a, b / 2, mod); return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}




ll q;
vector <pair <ll, ll>> child;
vector <ll> op, arr;


void breed(ll x, ll lx, ll rx){
    if ((child[x].first != 0) || (rx - lx == 1))
        return;
    child[x].first = child.size();
    child.push_back({0, 0});
    op.push_back(-1);
    arr.push_back(0);

    child[x].second = child.size();
    child.push_back({0, 0});
    op.push_back(-1);
    arr.push_back(0);
}

void propogate(ll x, ll lx, ll rx){
    breed(x, lx, rx);
    if (rx - lx == 1)
        return;
    if (op[x] == -1)
        return;
    ll a = child[x].first, b = child[x].second, mid = (lx + rx) / 2;
    arr[a] = (mid - lx) * op[x];
    arr[b] = (rx - mid) * op[x];
    op[a] = op[x];
    op[b] = op[x];
    op[x] = -1;
}

ll get(ll l, ll r, ll x, ll lx, ll rx){
    propogate(x, lx, rx);
    if (l >= rx || lx >= r)
        return 0; 
    if (l <= lx && rx <= r)
        return arr[x];
    ll a = child[x].first, b = child[x].second, mid = (lx + rx) / 2;
    return get(l, r, a, lx, mid) + get(l, r, b, mid, rx);
}

void setter(ll l, ll r, ll val, ll x, ll lx, ll rx){
    propogate(x, lx, rx);
    if (l >= rx || lx >= r)
        return;
    if (l <= lx && rx <= r){
        arr[x] = (rx - lx) * val;
        op[x] = val;
        return;
    }
    ll a = child[x].first, b = child[x].second, mid = (lx + rx) / 2;
    setter(l, r, val, a, lx, mid);
    setter(l, r, val, b, mid, rx);
    arr[x] = arr[a] + arr[b];
}




int main(){
sariE;// filE;



child.push_back({0, 0});
arr.push_back(0);
op.push_back(-1);
ll enc = 0;


cin >> q;
while (q--){
    ll chi, l, r; cin >> chi >> l >> r;
    l += enc;
    r += enc;
    if (chi == 1){
        ll ans = get(l, r + 1, 0, 0, 1e9 + 10);
        cout << ans << endl;
        enc = ans;
    }
    else{
        setter(l, r + 1, 1, 0, 0, 1e9 + 10);
    }
}





}

Compilation message (stderr)

apple.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization ("unroll-loops")
      | 
apple.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O1, O2, O3, Ofast")
      | 
apple.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("trapv")
      | 
apple.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("sse, sse2, sse3, sse4, sse4.1, sse4.2, avx")
      |

• Subtask 1: 100 / 100