oj.uz

답안 #667525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
667525 2022-12-01T16:50:53 Z bojackduy 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 263 ms 105356 KB 
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <functional>
#define task "task"
#define size() size() * 1ll 
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define numbit(x) __builtin_popcountll(x)

using namespace std;

typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

template<class t>
bool mini(t &x,t y) {
    if (y < x) {
       x = y;
       return 1;
    }
return 0;
}
template<class t>
bool maxi(t &x,t y) {
    if (x < y) {
       x = y;
       return 1;
    }
return 0;
}

const int N = 1e6 + 1;
const int M = 1e3 + 1;
const long long mod = 1e9 + 7;
const long long oo = 1e18 + 7;

struct node {
    int sum, lazy, lf, rg, l, r;
} st[64 * (int)(2e5 + 7)];
int cnt = 0;
void down(int id) {
    int &x = st[id].lazy;
    if (!x) return;
    int mid = st[id].l + st[id].r >> 1;
    if (!st[id].lf) {
        st[id].lf = ++cnt;
        st[cnt].l = st[id].l;
        st[cnt].r = mid;
    }
    st[st[id].lf].sum = x * (mid - st[id].l + 1);
    st[st[id].lf].lazy = x;

    if (!st[id].rg) {
        st[id].rg = ++cnt;
        st[cnt].l = mid + 1;
        st[cnt].r = st[id].r;
    }
    st[st[id].rg].sum = x * (st[id].r - mid);
    st[st[id].rg].lazy = x;
    x = 0;    
}
void adj(int id, int u, int v, int x) {
    if (u <= st[id].l && st[id].r <= v) {
        st[id].sum = (st[id].r - st[id].l + 1) * x;
        st[id].lazy = x;
    return ;
    }
    int mid = st[id].l + st[id].r >> 1;
    down(id);
    if (u <= mid) {
        if (!st[id].lf) {
            st[id].lf = ++cnt;
            st[cnt].l = st[id].l;
            st[cnt].r = mid;
        }
        adj(st[id].lf, u, v, x);
    }
    if (mid + 1 <= v) {
        if (!st[id].rg) {
            st[id].rg = ++cnt;
            st[cnt].l = mid + 1;
            st[cnt].r = st[id].r;
        }
        adj(st[id].rg, u, v, x);
    }
    st[id].sum = st[st[id].lf].sum + st[st[id].rg].sum;
}

int get(int id, int u, int v) {
    if (u <= st[id].l && st[id].r <= v) return st[id].sum;
    int mid = st[id].l + st[id].r >> 1;
    down(id);
    int lef = 0, rig = 0;
    if (u <= mid) {
        if (!st[id].lf) {
            st[id].lf = ++cnt;
            st[cnt].l = st[id].l;
            st[cnt].r = mid;
        }
        lef = get(st[id].lf, u, v);
    }
    if (mid + 1 <= v) {
        if (!st[id].rg) {
            st[id].rg = ++cnt;
            st[cnt].l = mid + 1;
            st[cnt].r = st[id].r;
        }
        rig = get(st[id].rg, u, v);
    }
return lef + rig;
}

void solve(int test = -1) {
    int n;
    cin >> n;
    st[1].l = 1, st[1].r = 1e9;
    cnt = 1;
    int ans = 0;
    while (n--) {
        int t, l, r, x = 1;
        cin >> t >> l >> r;
        l += ans;
        r += ans;
        if (t == 2) {
            adj(1, l, r, x);
        } else {
            ans = get(1, l, r);
            cout << ans << '\n';
        }
    }
}

int32_t main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen(task".inp", "r", stdin);
    // freopen(task".out", "w", stdout);

    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
return 0;
}
/*

*/

Compilation message

apple.cpp: In function 'void down(int)':
apple.cpp:53:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int mid = st[id].l + st[id].r >> 1;
      |               ~~~~~~~~~^~~~~~~~~~
apple.cpp: In function 'void adj(int, int, int, int)':
apple.cpp:77:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     int mid = st[id].l + st[id].r >> 1;
      |               ~~~~~~~~~^~~~~~~~~~
apple.cpp: In function 'int get(int, int, int)':
apple.cpp:100:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |     int mid = st[id].l + st[id].r >> 1;
      |               ~~~~~~~~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 12 ms 2612 KB Output is correct
5 Correct 11 ms 3028 KB Output is correct
6 Correct 11 ms 3028 KB Output is correct
7 Correct 11 ms 3040 KB Output is correct
8 Correct 78 ms 22056 KB Output is correct
9 Correct 175 ms 38688 KB Output is correct
10 Correct 198 ms 43940 KB Output is correct
11 Correct 177 ms 47076 KB Output is correct
12 Correct 195 ms 48568 KB Output is correct
13 Correct 178 ms 56384 KB Output is correct
14 Correct 166 ms 56916 KB Output is correct
15 Correct 251 ms 102304 KB Output is correct
16 Correct 250 ms 102972 KB Output is correct
17 Correct 170 ms 58784 KB Output is correct
18 Correct 176 ms 58836 KB Output is correct
19 Correct 263 ms 105296 KB Output is correct
20 Correct 238 ms 105356 KB Output is correct