oj.uz

Submission #115787

# Submission time Handle Problem Language Result Execution time Memory
115787 2019-06-09T06:04:34 Z gs18103 허수아비 (JOI14_scarecrows) C++
100 / 100
 255 ms 23156 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() {
	ios::sync_with_stdio(false); cin.tie(0);
	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 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 21648 KB Output is correct
2 Correct 255 ms 22388 KB Output is correct
3 Correct 159 ms 23156 KB Output is correct
4 Correct 144 ms 22372 KB Output is correct
5 Correct 171 ms 22324 KB Output is correct
6 Correct 197 ms 22392 KB Output is correct
7 Correct 222 ms 22344 KB Output is correct
8 Correct 242 ms 22416 KB Output is correct
9 Correct 117 ms 22392 KB Output is correct
10 Correct 179 ms 22648 KB Output is correct
11 Correct 202 ms 22316 KB Output is correct
12 Correct 225 ms 22388 KB Output is correct
13 Correct 232 ms 22428 KB Output is correct
14 Correct 122 ms 22316 KB Output is correct
15 Correct 204 ms 22396 KB Output is correct
16 Correct 232 ms 22320 KB Output is correct
17 Correct 130 ms 14356 KB Output is correct
18 Correct 219 ms 22416 KB Output is correct
19 Correct 211 ms 22424 KB Output is correct
20 Correct 217 ms 22308 KB Output is correct