Submission #950313

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
950313	2024-03-20T08:00:46 Z	nguyennh	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	304 ms	186704 KB

apple

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define el '\n'
using namespace std ;
 
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
	int sum, lazy, tl, tr, l, r;
	Node() : sum(0), lazy(0), l(-1), r(-1) {}
};
 
const int MAXN = 123456;
Node segtree[64 * MAXN];
int cnt = 2;
 
void push_lazy(int node) {
	if (segtree[node].lazy) {
		segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
		segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
		segtree[node].lazy = 0;
	}
}
 
void update(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr) {
		segtree[node].lazy = 1;
		push_lazy(node);
	} else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
 
		if (l > mid) update(segtree[node].r, l, r);
		else if (r <= mid) update(segtree[node].l, l, r);
		else {
			update(segtree[node].l, l, mid);
			update(segtree[node].r, mid + 1, r);
		}
 
		push_lazy(segtree[node].l);
		push_lazy(segtree[node].r);
		segtree[node].sum =
		    segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
	}
}
 
int query(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr)
		return segtree[node].sum;
	else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
 
		if (l > mid) return query(segtree[node].r, l, r);
		else if (r <= mid) return query(segtree[node].l, l, r);
		else
			return query(segtree[node].l, l, mid) +
			       query(segtree[node].r, mid + 1, r);
	}
}
 
int32_t main (){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int m;
  cin >> m;
  int last = 0;
  segtree[1].tl = 1;
  segtree[1].tr = (int)1e9;
  for ( int i = 1 ; i <= m ; i++ ){
    int type , l , r;
    cin >> type >> l >> r;
    l += last;
    r += last;
    if (type == 1){
      last = query(1 , l , r);
      cout << last << el;
    }
    else update(1 , l , r);
  }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	185940 KB	Output is correct
2	Correct	39 ms	185740 KB	Output is correct
3	Correct	40 ms	185740 KB	Output is correct
4	Correct	48 ms	185940 KB	Output is correct
5	Correct	57 ms	185904 KB	Output is correct
6	Correct	49 ms	185936 KB	Output is correct
7	Correct	50 ms	185940 KB	Output is correct
8	Correct	116 ms	186092 KB	Output is correct
9	Correct	208 ms	186368 KB	Output is correct
10	Correct	230 ms	186192 KB	Output is correct
11	Correct	216 ms	186336 KB	Output is correct
12	Correct	229 ms	186244 KB	Output is correct
13	Correct	187 ms	186452 KB	Output is correct
14	Correct	191 ms	186360 KB	Output is correct
15	Correct	287 ms	186436 KB	Output is correct
16	Correct	275 ms	186704 KB	Output is correct
17	Correct	196 ms	186288 KB	Output is correct
18	Correct	206 ms	186464 KB	Output is correct
19	Correct	275 ms	186284 KB	Output is correct
20	Correct	304 ms	186336 KB	Output is correct