oj.uz

답안 #742204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
742204 2023-05-15T18:59:30 Z Markomafko972 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 83 ms 65612 KB 
#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

# 결과 실행 시간 메모리 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