Submission #1098769

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098769	2024-10-09T23:32:02 Z	Ali_BBN	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	169 ms	71248 KB

apple

#include <bits/stdc++.h>
#define mp make_pair
#define ll long long
#define migmig cin.tie(NULL);ios_base::sync_with_stdio(false)
#define max_heap(T) priority_queue<T>
#define min_heap(T) priority_queue<T, vector<T>, greater<T>>
#define pb push_back
#define fi first
#define sec second
#define endl "\n"
#define pii pair <int, int>
using namespace std;
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const ll INF18 = 1e18;
const int MAXN = 7e7 + 1;
const int LOG = 23;
int node[MAXN], n = 1e9 + 1, lzy[MAXN], lft[MAXN], rgt[MAXN], now = 1;
ll get(int s, int e, int l = 0, int r = n, int id = 1){
	if (s <= l && e >= r) return node[id];
	if (s >= r || e <= l) return 0;
	int mid = (l + r) / 2;
    if (lft[id] == 0) lft[id] = ++now;
    if (rgt[id] == 0) rgt[id] = ++now;
    if (lzy[id]){
        lzy[lft[id]] = 1;
        lzy[rgt[id]] = 1;
        node[lft[id]] = mid - l;
        node[rgt[id]] = r - mid;
    }
    lzy[id] = 0;
    return get(s, e, l, mid, lft[id]) + get(s, e, mid, r, rgt[id]);
}
void upd(int s, int e, int l = 0, int r = n, int id = 1){
	if (s <= l && e >= r){
        lzy[id] = 1, node[id] = r - l;
        return;
    }
	if (s >= r || e <= l) return;
	int mid = (l + r) / 2;
    if (lft[id] == 0) lft[id] = ++now;
    if (rgt[id] == 0) rgt[id] = ++now;
    if (lzy[id]){
        lzy[lft[id]] = 1;
        lzy[rgt[id]] = 1;
        node[lft[id]] = mid - l;
        node[rgt[id]] = r - mid;
    }
    upd(s, e, l, mid, lft[id]);
    upd(s, e, mid, r, rgt[id]);
    node[id] = node[lft[id]] + node[rgt[id]];
}
void solve(){
	int m;
	cin >> m;
    int c = 0;
	for (int i = 0; i < m; i++){
		int d, l, r;
        cin >> d >> l >> r;
        l--;
        l += c, r += c;
        if (d == 1){
            c = get(l, r);
            cout << c << endl;
        }
        else upd(l, r);
	}
}
int main(){
	migmig;
	int tc = 1;
	// cin >> tc;
	for (int ti = 0; ti < tc; ti++) solve();
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	6 ms	2140 KB	Output is correct
5	Correct	8 ms	2340 KB	Output is correct
6	Correct	8 ms	2396 KB	Output is correct
7	Correct	7 ms	2512 KB	Output is correct
8	Correct	53 ms	15700 KB	Output is correct
9	Correct	111 ms	27472 KB	Output is correct
10	Correct	112 ms	30144 KB	Output is correct
11	Correct	122 ms	32568 KB	Output is correct
12	Correct	116 ms	33108 KB	Output is correct
13	Correct	107 ms	38540 KB	Output is correct
14	Correct	109 ms	38936 KB	Output is correct
15	Correct	163 ms	69276 KB	Output is correct
16	Correct	167 ms	69964 KB	Output is correct
17	Correct	124 ms	40152 KB	Output is correct
18	Correct	109 ms	40272 KB	Output is correct
19	Correct	169 ms	71184 KB	Output is correct
20	Correct	163 ms	71248 KB	Output is correct