Submission #742204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742204	2023-05-15T18:59:30 Z	Markomafko972	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	83 ms	65612 KB

apple

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, dod = 0;
int ty, poc, kr;

vector<int> sus[2000005];
pii p[2000005];
int t[2000005];
int slj = 1;

void update(int a, int b, int l, int r, int x) {
	p[x] = {l, r};
	//cout << x << ": " << l << " " << r << endl;
	
	if (b < l || r < a) return;
	if (a <= l && r <= b) {
		//cout << x << ": " << l << " " << r << endl;
		t[x] = r-l+1;
		return;
	}
	if (t[x] == r-l+1) return;
	
	int mid = (l+r)/2;
	
	for (int i = 0; i < sus[x].size(); i++) update(a, b, p[sus[x][i]].X, p[sus[x][i]].Y, sus[x][i]);
	
	if (sus[x].size() == 0 || (sus[x].size() == 1 && p[sus[x][0]].X != l)) {
		sus[x].push_back(slj);
		slj++;
		update(a, b, l, mid, slj-1);
	}
	
	if (sus[x].size() == 0 || (sus[x].size() == 1 && p[sus[x][0]].Y != r)) {
		sus[x].push_back(slj);
		slj++;
		update(a, b, mid+1, r, slj-1);
	}

	t[x] = t[sus[x][0]]+t[sus[x][1]];
}

int query(int a, int b, int l, int r, int x) {
	if (b < l || r < a) return 0;
	if (a <= l && r <= b) {
		return t[x];
	}
	
	if (t[x] == r-l+1) return min(b, r)-max(a, l)+1;
	
	int rj = 0;
	for (int i = 0; i < sus[x].size(); i++) rj += query(a, b, p[sus[x][i]].X, p[sus[x][i]].Y, sus[x][i]);
	return rj;
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	for (int i = 0; i < 2e6; i++) p[i] = {-1, -1};
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> ty >> poc >> kr;
		poc--, kr--;
		poc += dod, kr += dod;
		
		if (ty == 1) {
			int sol = query(poc, kr, 0, 1e9-1, 0);
			cout << sol << "\n";
			dod = sol;
		}
		else {
			update(poc, kr, 0, 1e9-1, 0);
		}
	}
	

	return 0;
}

Compilation message

apple.cpp: In function 'void update(int, int, int, int, int)':
apple.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0; i < sus[x].size(); i++) update(a, b, p[sus[x][i]].X, p[sus[x][i]].Y, sus[x][i]);
      |                  ~~^~~~~~~~~~~~~~~
apple.cpp: In function 'int query(int, int, int, int, int)':
apple.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i < sus[x].size(); i++) rj += query(a, b, p[sus[x][i]].X, p[sus[x][i]].Y, sus[x][i]);
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	62932 KB	Output is correct
2	Correct	31 ms	62932 KB	Output is correct
3	Correct	30 ms	62928 KB	Output is correct
4	Correct	35 ms	63064 KB	Output is correct
5	Correct	35 ms	63052 KB	Output is correct
6	Correct	34 ms	63076 KB	Output is correct
7	Correct	36 ms	63052 KB	Output is correct
8	Correct	51 ms	63992 KB	Output is correct
9	Correct	73 ms	65060 KB	Output is correct
10	Correct	79 ms	65100 KB	Output is correct
11	Correct	70 ms	65016 KB	Output is correct
12	Correct	69 ms	65108 KB	Output is correct
13	Correct	82 ms	65396 KB	Output is correct
14	Correct	83 ms	65444 KB	Output is correct
15	Correct	72 ms	65480 KB	Output is correct
16	Correct	68 ms	65612 KB	Output is correct
17	Correct	62 ms	65444 KB	Output is correct
18	Correct	59 ms	65480 KB	Output is correct
19	Correct	80 ms	65544 KB	Output is correct
20	Correct	71 ms	65532 KB	Output is correct