Submission #395567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
395567	2021-04-28T14:40:42 Z	dutinmeow	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	404 ms	134440 KB

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

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	15 ms	2624 KB	Output is correct
5	Correct	17 ms	2632 KB	Output is correct
6	Correct	18 ms	2632 KB	Output is correct
7	Correct	21 ms	2632 KB	Output is correct
8	Correct	113 ms	17528 KB	Output is correct
9	Correct	231 ms	34508 KB	Output is correct
10	Correct	260 ms	34448 KB	Output is correct
11	Correct	248 ms	34444 KB	Output is correct
12	Correct	250 ms	34356 KB	Output is correct
13	Correct	253 ms	68504 KB	Output is correct
14	Correct	257 ms	68544 KB	Output is correct
15	Correct	380 ms	134364 KB	Output is correct
16	Correct	364 ms	134376 KB	Output is correct
17	Correct	254 ms	68636 KB	Output is correct
18	Correct	271 ms	68504 KB	Output is correct
19	Correct	377 ms	134440 KB	Output is correct
20	Correct	404 ms	134424 KB	Output is correct