oj.uz

Submission #115493

# Submission time Handle Problem Language Result Execution time Memory
115493 2019-06-07T18:09:53 Z gs18103 허수아비 (JOI14_scarecrows) C++
100 / 100
 384 ms 23232 KB 
#include <bits/stdc++.h>

using namespace std;
#define x first
#define y second

pair <int, int> arr[202020];
int mst[20][202020];
long long ans = 0;

void update(vector <int> &tree, int i, int val) {
	while(i < tree.size()) {
		tree[i] = max(tree[i], val);
		i += (i & -i);
	}
}

int cal(vector <int> &tree, int i) {
	int re = 0;
	while(i > 0) {
		re = max(re, tree[i]);
		i -= (i & -i);
	}
	return re;
}

void merge(int s, int e, int dep) {
	if(s == e) {
		mst[dep][s] = s;
		return;
	}
	int m = (s + e) / 2;
	merge(s, m, dep+1); merge(m+1 ,e, dep+1);

	int d1 = s, d2 = m + 1, d = s;
	while(d1 <= m && d2 <= e) {
		if(arr[mst[dep+1][d1]].y < arr[mst[dep+1][d2]].y) mst[dep][d++] = mst[dep+1][d1++];
		else mst[dep][d++] = mst[dep+1][d2++];
	}
	while(d1 <= m) {
		mst[dep][d++] = mst[dep+1][d1++];
	}
	while(d2 <= e) {
		mst[dep][d++] = mst[dep+1][d2++];
	}
}

void dnc(int s, int e, int dep) {
	if(s == e) return;
	int m = (s + e) / 2;
	int d1 = s, d2 = m + 1;
	long long re = 0;
	vector <pair <int, int> > l, r;
	vector <int> tree;
	tree.resize(e - s + 5);
	for(; d2 <= e; d2++) {
		//cout << arr[mst[dep][d1]].y << " " << arr[mst[dep][d2]].y << endl;
		while(d1 <= m && arr[mst[dep][d1]].y < arr[mst[dep][d2]].y) {
			while(!l.empty()) {
				//cout << l[l.size()-1].x << " " << mst[dep][d1] << endl;
				if(l[l.size()-1].y > mst[dep][d1]) break;
				l.pop_back();
			}
			l.push_back(make_pair(arr[mst[dep][d1]].y, mst[dep][d1]));
			d1++;
		}
		//cout << l.size() << endl;
		re += (int)(l.end() - upper_bound(l.begin(), l.end(), make_pair(cal(tree, mst[dep][d2] - m), 0)));
		update(tree, mst[dep][d2] - m, arr[mst[dep][d2]].y);
	}
	//cout << s << " " << e << " " << re << endl;
	ans += re;
	dnc(s, m, dep+1);
	dnc(m+1, e, dep+1);
}

int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> arr[i].x >> arr[i].y;
	}
	sort(arr+1, arr+n+1);
	merge(1, n, 0);
	/*for(int i = 0; i < 5; i++) {
		for(int j = 1; j <= n; j++) {
			cout << mst[i][j] << " ";
		}
		cout << endl;
	}*/
	dnc(1, n, 1);
	cout << ans;
}

Compilation message

scarecrows.cpp: In function 'void update(std::vector<int>&, int, int)':
scarecrows.cpp:12:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < tree.size()) {
        ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 9 ms 896 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 13 ms 896 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 9 ms 896 KB Output is correct
8 Correct 8 ms 1024 KB Output is correct
9 Correct 9 ms 932 KB Output is correct
10 Correct 9 ms 896 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 8 ms 768 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 19764 KB Output is correct
2 Correct 361 ms 20964 KB Output is correct
3 Correct 280 ms 23232 KB Output is correct
4 Correct 266 ms 22324 KB Output is correct
5 Correct 295 ms 22496 KB Output is correct
6 Correct 312 ms 22392 KB Output is correct
7 Correct 344 ms 22468 KB Output is correct
8 Correct 364 ms 22372 KB Output is correct
9 Correct 247 ms 22416 KB Output is correct
10 Correct 349 ms 22648 KB Output is correct
11 Correct 374 ms 22520 KB Output is correct
12 Correct 384 ms 22396 KB Output is correct
13 Correct 377 ms 22440 KB Output is correct
14 Correct 267 ms 22296 KB Output is correct
15 Correct 337 ms 22496 KB Output is correct
16 Correct 381 ms 22320 KB Output is correct
17 Correct 211 ms 14452 KB Output is correct
18 Correct 342 ms 22508 KB Output is correct
19 Correct 373 ms 22324 KB Output is correct
20 Correct 330 ms 22400 KB Output is correct