Submission #667525

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
667525	2022-12-01T16:50:53 Z	bojackduy	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	263 ms	105356 KB

apple

#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

#	Verdict	Execution time	Memory	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