# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
27890 | 2017-07-14T11:07:51 Z | suhgyuho_william | Port Facility (JOI17_port_facility) | C++14 | 0 ms | 26432 KB |
#include <bits/stdc++.h> #define lld long long #define pii pair<int,int> #define pll pair<lld,lld> #define pb push_back #define next nextt #define left leftt #define right rightt #define Inf 1000000000 #define Linf 1000000000000000000LL #define Mod 1000000007LL using namespace std; int N; lld ans,inv; struct data{ int x,y; bool operator < (const data &cmp) const{ if(x != cmp.x) return x < cmp.x; return y < cmp.y; } }a[2000002],in[1000002]; bool check[1000002]; void dfs(int x){ check[x] = true; for(int i=x+1; i<=N; i++){ if(check[i]) continue; if(a[x].x < a[i].x && a[i].x < a[x].y && a[x].y < a[i].y) dfs(i); } for(int i=1; i<x; i++){ if(check[i]) continue; if(a[i].x < a[x].x && a[x].x < a[i].y && a[i].y < a[x].y) dfs(i); } } int main(){ scanf("%d",&N); ans = 1; for(int i=1; i<=N; i++){ scanf("%d %d",&a[i].x,&a[i].y); a[i+N].x = a[i].y; a[i+N].y = -a[i].y; in[i].x = a[i].x; in[i].y = a[i].y; } sort(a+1,a+N*2+1); { vector<int> t1,t2; for(int i=1; i<=N*2; i++){ break; if(a[i].y > 0){ if(t1.size() == 0) t1.pb(a[i].y); else if(t2.size() == 0) t2.pb(a[i].y); else if(t1.back() < t2.back() && t1.back() > a[i].y) t1.pb(a[i].y); else if(t2.back() < t1.back() && t2.back() > a[i].y) t2.pb(a[i].y); else if(t1.back() > a[i].y) t1.pb(a[i].y); else if(t2.back() > a[i].y) t2.pb(a[i].y); else{ puts("0"); return 0; } }else{ if(t1.size() != 0 && t1.back() == -a[i].y) t1.pop_back(); else t2.pop_back(); } } } for(int i=1; i<=N; i++) a[i] = in[i]; sort(a+1,a+N+1); for(int i=1; i<=N; i++){ if(check[i]) continue; dfs(i); ans *= 2; ans %= Mod; } printf("%lld\n",ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 26432 KB | Output is correct |
2 | Correct | 0 ms | 26432 KB | Output is correct |
3 | Correct | 0 ms | 26432 KB | Output is correct |
4 | Correct | 0 ms | 26432 KB | Output is correct |
5 | Correct | 0 ms | 26432 KB | Output is correct |
6 | Correct | 0 ms | 26432 KB | Output is correct |
7 | Correct | 0 ms | 26432 KB | Output is correct |
8 | Correct | 0 ms | 26432 KB | Output is correct |
9 | Correct | 0 ms | 26432 KB | Output is correct |
10 | Correct | 0 ms | 26432 KB | Output is correct |
11 | Incorrect | 0 ms | 26432 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 26432 KB | Output is correct |
2 | Correct | 0 ms | 26432 KB | Output is correct |
3 | Correct | 0 ms | 26432 KB | Output is correct |
4 | Correct | 0 ms | 26432 KB | Output is correct |
5 | Correct | 0 ms | 26432 KB | Output is correct |
6 | Correct | 0 ms | 26432 KB | Output is correct |
7 | Correct | 0 ms | 26432 KB | Output is correct |
8 | Correct | 0 ms | 26432 KB | Output is correct |
9 | Correct | 0 ms | 26432 KB | Output is correct |
10 | Correct | 0 ms | 26432 KB | Output is correct |
11 | Incorrect | 0 ms | 26432 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 26432 KB | Output is correct |
2 | Correct | 0 ms | 26432 KB | Output is correct |
3 | Correct | 0 ms | 26432 KB | Output is correct |
4 | Correct | 0 ms | 26432 KB | Output is correct |
5 | Correct | 0 ms | 26432 KB | Output is correct |
6 | Correct | 0 ms | 26432 KB | Output is correct |
7 | Correct | 0 ms | 26432 KB | Output is correct |
8 | Correct | 0 ms | 26432 KB | Output is correct |
9 | Correct | 0 ms | 26432 KB | Output is correct |
10 | Correct | 0 ms | 26432 KB | Output is correct |
11 | Incorrect | 0 ms | 26432 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 26432 KB | Output is correct |
2 | Correct | 0 ms | 26432 KB | Output is correct |
3 | Correct | 0 ms | 26432 KB | Output is correct |
4 | Correct | 0 ms | 26432 KB | Output is correct |
5 | Correct | 0 ms | 26432 KB | Output is correct |
6 | Correct | 0 ms | 26432 KB | Output is correct |
7 | Correct | 0 ms | 26432 KB | Output is correct |
8 | Correct | 0 ms | 26432 KB | Output is correct |
9 | Correct | 0 ms | 26432 KB | Output is correct |
10 | Correct | 0 ms | 26432 KB | Output is correct |
11 | Incorrect | 0 ms | 26432 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |