Submission #115419

#	Time	Username	Problem	Language	Result	Execution time	Memory
115419		gs18103	허수아비 (JOI14_scarecrows)	C++98	0 / 100	221 ms	5940 KiB

scarecrows

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 85