Submission #667523

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
667523	2022-12-01T16:49:46 Z	bojackduy	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	103 ms	49512 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[N];
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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	10 ms	2648 KB	Output is correct
5	Correct	12 ms	3284 KB	Output is correct
6	Correct	14 ms	3160 KB	Output is correct
7	Correct	12 ms	3296 KB	Output is correct
8	Correct	79 ms	22884 KB	Output is correct
9	Runtime error	103 ms	49512 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-