답안 #963505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963505 2024-04-15T07:46:48 Z Esgeer 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
2000 ms 151168 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 = 1e5+5;

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

Node t[64*N];
int idx = 0;

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 = ++idx;
        t[idx].tl = t[node].tl;
        t[idx].tr = mid;
    }
    if(t[node].r == -1) {
        t[node].r = ++idx;
        t[idx].tl = mid+1;
        t[idx].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 = ++idx;
            t[idx].tl = t[node].tl;
            t[idx].tr = mid;
        }
        if(t[node].r == -1) {
            t[node].r = ++idx;
            t[idx].tl = mid+1;
            t[idx].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
        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 = ++idx;
        t[idx].tl = t[node].tl;
        t[idx].tr = mid;
    }
    if(t[node].r == -1) {
        t[node].r = ++idx;
        t[idx].tl = mid+1;
        t[idx].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();
}
# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 150612 KB Output is correct
2 Correct 37 ms 150616 KB Output is correct
3 Correct 36 ms 150552 KB Output is correct
4 Correct 40 ms 150608 KB Output is correct
5 Correct 47 ms 150624 KB Output is correct
6 Correct 45 ms 150724 KB Output is correct
7 Correct 42 ms 150712 KB Output is correct
8 Correct 101 ms 150864 KB Output is correct
9 Correct 193 ms 151120 KB Output is correct
10 Correct 221 ms 151088 KB Output is correct
11 Correct 220 ms 151124 KB Output is correct
12 Correct 251 ms 150884 KB Output is correct
13 Correct 185 ms 151168 KB Output is correct
14 Correct 212 ms 151088 KB Output is correct
15 Execution timed out 2029 ms 151120 KB Time limit exceeded
16 Halted 0 ms 0 KB -