Submission #395567

#	Time	Username	Problem	Language	Result	Execution time	Memory
395567		dutinmeow	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	404 ms	134440 KiB

apple

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

typedef int_fast8_t  int8;
typedef int_fast16_t int16;
typedef int_fast32_t int32;
typedef int_fast64_t int64;
typedef int_fast64_t ll;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll>   pll;
typedef pair<ll, pll>  plll;

#define PB push_back
#define PF push_front
#define MP make_pair
#define FF first
#define SS second

struct node {
    int S, L, LC, RC;

    node(int S, int L, int LC, int RC) : S(S), L(L), LC(LC), RC(RC) {}
    
    node(int S, int L) : S(S), L(L), LC(-1), RC(-1) {}

    node() : S(0), L(0), LC(-1), RC(-1) {}
};

inline ostream& operator<<(ostream& os, const node& n) { 
    return os << '{' << n.S << ',' << n.L << ',' << n.LC << ',' << n.RC << '}';
}

int Q, C = 0;
vector<node> T;

void pushdown(int t, int tl, int tr) {
    if (T[t].L) {
        int tm = (tl + tr) >> 1;

        if (T[t].LC == -1) 
            T[t].LC = T.size(), T.PB(node());
        T[T[t].LC].S = (tm - tl + 1) * T[t].L;
        T[T[t].LC].L = T[t].L;

        if (T[t].RC == -1)
            T[t].RC = T.size(), T.PB(node());
        T[T[t].RC].S = (tr - tm) * T[t].L;
        T[T[t].RC].L = T[t].L;

        T[t].L = 0;
    }
}

void update(int l, int r, int v, int t = 0, int tl = 1, int tr = 1000000000) {
    assert(t != -1);
    //cout << t << ' ' << tl << ' ' << tr << '\n';
    if (r < tl || tr < l || tr < tl)
        return;
    if (l <= tl && tr <= r) {
        T[t].S = (tr - tl + 1) * v, T[t].L = v;
        return;
    }
    if (tl != tr)
        pushdown(t, tl, tr);

    int tm = (tl + tr) >> 1;
    if (l <= tm) {
        if (T[t].LC == -1)
            T[t].LC = T.size(), T.PB(node());
        update(l, r, v, T[t].LC, tl, tm);
    }
    if (tm < r) {
        if (T[t].RC == -1)
            T[t].RC = T.size(), T.PB(node());
        update(l, r, v, T[t].RC, tm + 1, tr);
    }
    int sl = T[t].LC == -1 ? 0 : T[T[t].LC].S;
    int sr = T[t].RC == -1 ? 0 : T[T[t].RC].S;
    T[t].S = sl + sr;
}

int query(int l, int r, int t = 0, int tl = 1, int tr = 1000000000) {
    if (r < tl || tr < l || tr < tl)
        return 0;
    if (l <= tl && tr <= r)
        return T[t].S;
    if (tl != tr)
        pushdown(t, tl, tr);
    
    int tm = (tl + tr) >> 1;
    int sl = T[t].LC == -1 ? 0 : query(l, r, T[t].LC, tl, tm);
    int sr = T[t].RC == -1 ? 0 : query(l, r, T[t].RC, tm + 1, tr);
    return sl + sr;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    T.PB(node());
    
    cin >> Q;
    while (Q--) {
        int t, l, r; cin >> t >> l >> r;
        if (t == 1) 
            cout << (C = query(l + C, r + C)) << '\n';
        else if (t == 2)
            update(l + C, r + C, 1);

        /*
        for (int i = 0; i < T.size(); i++)
            cout << i << ' ' << T[i] << '\n';
        cout << '\n';
        */
    }
}

Compilation message (stderr)

apple.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 100 / 100