oj.uz

Submission #115419

# Submission time Handle Problem Language Result Execution time Memory
115419 2019-06-07T10:58:21 Z gs18103 허수아비 (JOI14_scarecrows) C++
0 / 100
 221 ms 5940 KB 
#include <bits/stdc++.h>

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

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

void dnc(int s, int e) {
	if(s == e) return;
	int m = (s + e) / 2;

	stack <int> l, r;
	for(int i = m; i >= s; i--) {
		if(l.empty()) l.push(arr[i].y);
		else if(l.top() < arr[i].y) l.push(arr[i].y);
	}
	int ty = 2000000000, re = 0;
	for(int i = m + 1; i <= e; i++) {
		if(arr[i].y < ty) ty = arr[i].y;
		else continue;
		while(!l.empty() && l.top() > ty) {
			l.pop();
		}
		ans += l.size();
	}
	dnc(s, m);
	dnc(m+1, e);
}

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);
	dnc(1, n);
	cout << ans;
}

Compilation message

scarecrows.cpp: In function 'void dnc(int, int)':
scarecrows.cpp:19:23: warning: unused variable 're' [-Wunused-variable]
  int ty = 2000000000, re = 0;
                       ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Incorrect 8 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 5268 KB Output is correct
2 Incorrect 221 ms 5940 KB Output isn't correct
3 Halted 0 ms 0 KB -