# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
48267 | 2018-05-11T07:42:57 Z | choikiwon | 허수아비 (JOI14_scarecrows) | C++17 | 4000 ms | 262144 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MN = 200010; const int SQ = 400; const int BS = (MN + SQ - 1) / SQ; int N; pii P[MN]; vector<pii> X, Y; int invx[MN], invy[MN]; vector<pii> stk[BS]; int solve(int x) { int p = (P[x].second + SQ - 1) / SQ; vector<int> tmp; for(int i = min(N, p * SQ) - 1; i > P[x].second; i--) { if(invy[i] > x) { while(tmp.size() && tmp.back() >= invy[i]) tmp.pop_back(); tmp.push_back(invy[i]); } } if(tmp.size() == 0) { return stk[p].size(); } int s = 0, e = (int)stk[p].size() - 1, k = (int)stk[p].size(); while(s <= e) { int m = (s + e)>>1; if(stk[p][m].first < tmp[0]) { k = m; e = m - 1; } else s = m + 1; } return (int)stk[p].size() - k + (int)tmp.size(); } int main() { scanf("%d", &N); for(int i = 0; i < N; i++) { scanf("%d %d", &P[i].first, &P[i].second); X.push_back({ P[i].first, i }); Y.push_back({ P[i].second, i }); } sort(X.begin(), X.end()); sort(Y.begin(), Y.end()); for(int i = 0; i < N; i++) { P[ X[i].second ].first = i; P[ Y[i].second ].second = i; } for(int i = 0; i < N; i++) { invx[ P[i].first ] = P[i].second; invy[ P[i].second ] = P[i].first; } sort(P, P + N); ll ans = 0; for(int i = N - 1; i >= 0; i--) { ans += solve(i); for(int j = 0; j < BS; j++) { if(j * SQ > P[i].second) break; while(stk[j].size() && stk[j].back().second >= P[i].second) stk[j].pop_back(); stk[j].push_back(P[i]); } } printf("%lld", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
2 | Correct | 2 ms | 380 KB | Output is correct |
3 | Correct | 2 ms | 548 KB | Output is correct |
4 | Correct | 2 ms | 548 KB | Output is correct |
5 | Correct | 2 ms | 604 KB | Output is correct |
6 | Correct | 2 ms | 604 KB | Output is correct |
7 | Correct | 2 ms | 704 KB | Output is correct |
8 | Correct | 3 ms | 824 KB | Output is correct |
9 | Correct | 2 ms | 824 KB | Output is correct |
10 | Correct | 2 ms | 976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1256 KB | Output is correct |
2 | Correct | 13 ms | 1256 KB | Output is correct |
3 | Correct | 8 ms | 1404 KB | Output is correct |
4 | Correct | 8 ms | 1404 KB | Output is correct |
5 | Correct | 9 ms | 1472 KB | Output is correct |
6 | Correct | 12 ms | 1572 KB | Output is correct |
7 | Correct | 12 ms | 1672 KB | Output is correct |
8 | Correct | 6 ms | 2160 KB | Output is correct |
9 | Correct | 14 ms | 2160 KB | Output is correct |
10 | Correct | 12 ms | 2160 KB | Output is correct |
11 | Correct | 13 ms | 2160 KB | Output is correct |
12 | Correct | 7 ms | 2172 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 4128 ms | 262144 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |