# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
115419 | 2019-06-07T10:58:21 Z | gs18103 | 허수아비 (JOI14_scarecrows) | C++ | 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
# | 결과 | 실행 시간 | 메모리 | 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | - |