oj.uz

답안 #963514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963514 2024-04-15T08:00:39 Z Esgeer 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 335 ms 199620 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <unistd.h>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
#endif
//#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp << " " <<
#define F(i, s, n) for(int i = s; i < n; i++)
#define pb push_back
#define fi first
#define se second

int mod = 1e9+7;
int inf = 1e6;
const int N = 123456;

struct Node {
    int sum, lazy, l, r, tl, tr;
    Node() : sum(0), lazy(0), l(-1), r(-1) {}  
};

vector<Node> t(1);

void push(int node) {
    if(t[node].lazy == 0) return;
    t[node].sum = t[node].tr - t[node].tl + 1;

    int mid = (t[node].tl + t[node].tr) >> 1;

    if(t[node].l == -1) {
        t[node].l = t.size();
        t.pb({});
        t.back().tl = t[node].tl;
        t.back().tr = mid;
    }
    if(t[node].r == -1) {
        t[node].r = t.size();
        t.pb({});
        t.back().tl = mid+1;
        t.back().tr = t[node].tr;
    }

    t[t[node].l].lazy = 1;
    t[t[node].r].lazy = 1;
    t[node].lazy = 0;
}

void update(int node, int l, int r) {
    push(node);
    if(t[node].tl == l && t[node].tr == r) {
        t[node].lazy = 1;
        push(node);
    } else {
        int mid = (t[node].tl + t[node].tr) >> 1;

        if(t[node].l == -1) {
            t[node].l = t.size();
            t.pb({});
            t.back().tl = t[node].tl;
            t.back().tr = mid;
        }
        if(t[node].r == -1) {
            t[node].r = t.size();
            t.pb({});
            t.back().tl = mid+1;
            t.back().tr = t[node].tr;
        }

        if(l > mid) update(t[node].r, l, r);
        else if(r <= mid) update(t[node].l, l, r);
        else {
            update(t[node].l, l, mid);
            update(t[node].r, mid+1, r);
        }
        // REMOVED UNNECESSARY PUSH OPERATIONS - seems like they re necessary :/
        push(t[node].l);
        push(t[node].r);
        t[node].sum = t[t[node].l].sum + t[t[node].r].sum;
    }
}

int query(int node, int l, int r) {
    push(node);
    if(t[node].tl == l && t[node].tr == r) return t[node].sum;
    int mid = (t[node].tl + t[node].tr) >> 1;

    if(t[node].l == -1) {
        t[node].l = t.size();
        t.pb({});
        t.back().tl = t[node].tl;
        t.back().tr = mid;
    }
    if(t[node].r == -1) {
        t[node].r = t.size();
        t.pb({});
        t.back().tl = mid+1;
        t.back().tr = t[node].tr;
    }

    if(l > mid) return query(t[node].r, l, r);
    else if(r <= mid) return query(t[node].l, l, r);
    else return query(t[node].l, l, mid) + query(t[node].r, mid+1, r);
}

void solve() {
    int n;
    cin >> n;
    t[0].tl = 0;
    t[0].tr = 1e9;
    t[0].sum = 0;
    t[0].lazy = 0;
    t[0].l = -1;
    t[0].r = -1;

    int c = 0;

    F(i, 0, n) {
        int type, a, b;
        cin >> type >> a >> b;
        if(type == 1) {
            c = query(0, a + c, b + c);
            cout << c << endl;
        } else update(0, a + c, b + c);
    }
}

void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Local
        freopen("local.in", "r", stdin);
        freopen("local.out", "w", stdout);
    #else 
        // freopen("poetry.in","r",stdin);
        // freopen("poetry.out","w",stdout);
    #endif
}

signed main() {
    setIO();
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 12 ms 6848 KB Output is correct
5 Correct 15 ms 7112 KB Output is correct
6 Correct 13 ms 8904 KB Output is correct
7 Correct 14 ms 8392 KB Output is correct
8 Correct 107 ms 51092 KB Output is correct
9 Correct 223 ms 99316 KB Output is correct
10 Correct 218 ms 100292 KB Output is correct
11 Correct 225 ms 101132 KB Output is correct
12 Correct 223 ms 100760 KB Output is correct
13 Correct 199 ms 100764 KB Output is correct
14 Correct 206 ms 99232 KB Output is correct
15 Correct 335 ms 198028 KB Output is correct
16 Correct 329 ms 199044 KB Output is correct
17 Correct 201 ms 99888 KB Output is correct
18 Correct 217 ms 101436 KB Output is correct
19 Correct 316 ms 199620 KB Output is correct
20 Correct 332 ms 198516 KB Output is correct