# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

23984 | 2017-05-28T14:51:54 Z | gs14004 | Port Facility (JOI17_port_facility) | C++11 | 2863 ms | 125900 KB |

#include <bits/stdc++.h> using namespace std; typedef long long lint; typedef pair<lint, lint> pi; const int mod = 1e9 + 7; struct seg2{ int tree[4200000], lim; void init(int n){ for(lim = 1; lim <= n; lim <<= 1); fill(tree, tree + 2 * lim + 1, -1e9); } void add(int x, int v){ x += lim; tree[x] = v; while(x > 1){ x >>= 1; tree[x] = max(tree[2*x], tree[2*x+1]); } } int query(int s, int e){ s += lim; e += lim; int ret = -1e9; while(s < e){ if(s%2 == 1) ret = max(ret, tree[s++]); if(e%2 == 0) ret = max(ret, tree[e--]); s >>= 1; e >>= 1; } if(s == e) ret = max(ret, tree[s]); return ret; } }seg1, seg2; int n, s[1000005], e[1000005]; int idx[2000005]; int col[1000005]; void dfs(int x, int c){ // fprintf(stderr, "%d\n", x); col[x] = c; while(1){ int t = seg1.query(s[x] + 1, e[x] - 1); if(t <= e[x]) break; int v = idx[t]; seg1.add(s[v], -1); seg2.add(e[v], -1e9); dfs(v, 3-c); } while(1){ int t = -seg2.query(s[x] + 1, e[x] - 1); if(t >= s[x]) break; int v = idx[t]; seg1.add(s[v], -1); seg2.add(e[v], -1e9); dfs(v, 3-c); } } bool solve(vector<pi> &v){ sort(v.begin(), v.end()); stack<pi> stk; for(int i=0; i<v.size(); i++){ while(!stk.empty() && stk.top().second < v[i].first){ stk.pop(); } if(!stk.empty() && stk.top().second > v[i].first && stk.top().second < v[i].second){ return 0; } stk.push(v[i]); } return 1; } int main(){ scanf("%d",&n); seg1.init(2*n); seg2.init(2*n); for(int i=0; i<n; i++){ scanf("%d %d",&s[i],&e[i]); idx[s[i]] = i; idx[e[i]] = i; seg1.add(s[i], e[i]); seg2.add(e[i], -s[i]); } lint ans = 1; for(int i=1; i<=2*n; i++){ if(!col[idx[i]]){ seg1.add(s[idx[i]], -1); seg2.add(e[idx[i]], -1e9); dfs(idx[i], 1); ans *= 2; ans %= mod; } } vector<pi> l, r; for(int i=0; i<n; i++){ if(col[i] == 1) l.push_back(pi(s[i], e[i])); else r.push_back(pi(s[i], e[i])); } if(!solve(l) || !solve(r)) ans = 0; cout << ans; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 54368 KB | Output is correct |

2 | Correct | 0 ms | 54368 KB | Output is correct |

3 | Correct | 0 ms | 54368 KB | Output is correct |

4 | Correct | 0 ms | 54368 KB | Output is correct |

5 | Correct | 0 ms | 54368 KB | Output is correct |

6 | Correct | 0 ms | 54368 KB | Output is correct |

7 | Correct | 0 ms | 54368 KB | Output is correct |

8 | Correct | 0 ms | 54368 KB | Output is correct |

9 | Correct | 0 ms | 54368 KB | Output is correct |

10 | Correct | 0 ms | 54368 KB | Output is correct |

11 | Correct | 0 ms | 54368 KB | Output is correct |

12 | Correct | 0 ms | 54368 KB | Output is correct |

13 | Correct | 0 ms | 54368 KB | Output is correct |

14 | Correct | 0 ms | 54368 KB | Output is correct |

15 | Correct | 0 ms | 54368 KB | Output is correct |

16 | Correct | 0 ms | 54368 KB | Output is correct |

17 | Correct | 0 ms | 54368 KB | Output is correct |

18 | Correct | 0 ms | 54368 KB | Output is correct |

19 | Correct | 0 ms | 54368 KB | Output is correct |

20 | Correct | 0 ms | 54368 KB | Output is correct |

21 | Correct | 0 ms | 54368 KB | Output is correct |

22 | Correct | 0 ms | 54368 KB | Output is correct |

23 | Correct | 0 ms | 54368 KB | Output is correct |

24 | Correct | 0 ms | 54368 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 54368 KB | Output is correct |

2 | Correct | 0 ms | 54368 KB | Output is correct |

3 | Correct | 0 ms | 54368 KB | Output is correct |

4 | Correct | 0 ms | 54368 KB | Output is correct |

5 | Correct | 0 ms | 54368 KB | Output is correct |

6 | Correct | 0 ms | 54368 KB | Output is correct |

7 | Correct | 0 ms | 54368 KB | Output is correct |

8 | Correct | 0 ms | 54368 KB | Output is correct |

9 | Correct | 0 ms | 54368 KB | Output is correct |

10 | Correct | 0 ms | 54368 KB | Output is correct |

11 | Correct | 0 ms | 54368 KB | Output is correct |

12 | Correct | 0 ms | 54368 KB | Output is correct |

13 | Correct | 0 ms | 54368 KB | Output is correct |

14 | Correct | 0 ms | 54368 KB | Output is correct |

15 | Correct | 0 ms | 54368 KB | Output is correct |

16 | Correct | 0 ms | 54368 KB | Output is correct |

17 | Correct | 0 ms | 54368 KB | Output is correct |

18 | Correct | 0 ms | 54368 KB | Output is correct |

19 | Correct | 0 ms | 54368 KB | Output is correct |

20 | Correct | 0 ms | 54368 KB | Output is correct |

21 | Correct | 0 ms | 54368 KB | Output is correct |

22 | Correct | 0 ms | 54368 KB | Output is correct |

23 | Correct | 0 ms | 54368 KB | Output is correct |

24 | Correct | 0 ms | 54368 KB | Output is correct |

25 | Correct | 0 ms | 54528 KB | Output is correct |

26 | Correct | 0 ms | 54528 KB | Output is correct |

27 | Correct | 0 ms | 54528 KB | Output is correct |

28 | Correct | 0 ms | 54528 KB | Output is correct |

29 | Correct | 0 ms | 54528 KB | Output is correct |

30 | Correct | 0 ms | 54528 KB | Output is correct |

31 | Correct | 0 ms | 54520 KB | Output is correct |

32 | Correct | 0 ms | 54528 KB | Output is correct |

33 | Correct | 0 ms | 54528 KB | Output is correct |

34 | Correct | 3 ms | 54520 KB | Output is correct |

35 | Correct | 0 ms | 54508 KB | Output is correct |

36 | Correct | 0 ms | 54508 KB | Output is correct |

37 | Correct | 0 ms | 54500 KB | Output is correct |

38 | Correct | 0 ms | 54368 KB | Output is correct |

39 | Correct | 0 ms | 54504 KB | Output is correct |

40 | Correct | 0 ms | 54508 KB | Output is correct |

41 | Correct | 0 ms | 54368 KB | Output is correct |

42 | Correct | 0 ms | 54368 KB | Output is correct |

43 | Correct | 0 ms | 54368 KB | Output is correct |

44 | Correct | 0 ms | 54368 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 54368 KB | Output is correct |

2 | Correct | 0 ms | 54368 KB | Output is correct |

3 | Correct | 0 ms | 54368 KB | Output is correct |

4 | Correct | 0 ms | 54368 KB | Output is correct |

5 | Correct | 0 ms | 54368 KB | Output is correct |

6 | Correct | 0 ms | 54368 KB | Output is correct |

7 | Correct | 0 ms | 54368 KB | Output is correct |

8 | Correct | 0 ms | 54368 KB | Output is correct |

9 | Correct | 0 ms | 54368 KB | Output is correct |

10 | Correct | 0 ms | 54368 KB | Output is correct |

11 | Correct | 0 ms | 54368 KB | Output is correct |

12 | Correct | 0 ms | 54368 KB | Output is correct |

13 | Correct | 0 ms | 54368 KB | Output is correct |

14 | Correct | 0 ms | 54368 KB | Output is correct |

15 | Correct | 0 ms | 54368 KB | Output is correct |

16 | Correct | 0 ms | 54368 KB | Output is correct |

17 | Correct | 0 ms | 54368 KB | Output is correct |

18 | Correct | 0 ms | 54368 KB | Output is correct |

19 | Correct | 0 ms | 54368 KB | Output is correct |

20 | Correct | 0 ms | 54368 KB | Output is correct |

21 | Correct | 0 ms | 54368 KB | Output is correct |

22 | Correct | 0 ms | 54368 KB | Output is correct |

23 | Correct | 0 ms | 54368 KB | Output is correct |

24 | Correct | 0 ms | 54368 KB | Output is correct |

25 | Correct | 0 ms | 54528 KB | Output is correct |

26 | Correct | 0 ms | 54528 KB | Output is correct |

27 | Correct | 0 ms | 54528 KB | Output is correct |

28 | Correct | 0 ms | 54528 KB | Output is correct |

29 | Correct | 0 ms | 54528 KB | Output is correct |

30 | Correct | 0 ms | 54528 KB | Output is correct |

31 | Correct | 0 ms | 54520 KB | Output is correct |

32 | Correct | 0 ms | 54528 KB | Output is correct |

33 | Correct | 0 ms | 54528 KB | Output is correct |

34 | Correct | 3 ms | 54520 KB | Output is correct |

35 | Correct | 0 ms | 54508 KB | Output is correct |

36 | Correct | 0 ms | 54508 KB | Output is correct |

37 | Correct | 0 ms | 54500 KB | Output is correct |

38 | Correct | 0 ms | 54368 KB | Output is correct |

39 | Correct | 0 ms | 54504 KB | Output is correct |

40 | Correct | 0 ms | 54508 KB | Output is correct |

41 | Correct | 0 ms | 54368 KB | Output is correct |

42 | Correct | 0 ms | 54368 KB | Output is correct |

43 | Correct | 0 ms | 54368 KB | Output is correct |

44 | Correct | 0 ms | 54368 KB | Output is correct |

45 | Correct | 119 ms | 57632 KB | Output is correct |

46 | Correct | 139 ms | 58268 KB | Output is correct |

47 | Correct | 156 ms | 57196 KB | Output is correct |

48 | Correct | 149 ms | 58252 KB | Output is correct |

49 | Correct | 109 ms | 57288 KB | Output is correct |

50 | Correct | 109 ms | 58084 KB | Output is correct |

51 | Correct | 146 ms | 58072 KB | Output is correct |

52 | Correct | 99 ms | 57524 KB | Output is correct |

53 | Correct | 103 ms | 58096 KB | Output is correct |

54 | Correct | 129 ms | 61576 KB | Output is correct |

55 | Correct | 159 ms | 59232 KB | Output is correct |

56 | Correct | 123 ms | 59232 KB | Output is correct |

57 | Correct | 79 ms | 57016 KB | Output is correct |

58 | Correct | 109 ms | 57524 KB | Output is correct |

59 | Correct | 106 ms | 57780 KB | Output is correct |

60 | Correct | 129 ms | 58548 KB | Output is correct |

61 | Correct | 126 ms | 57100 KB | Output is correct |

62 | Correct | 96 ms | 57780 KB | Output is correct |

63 | Correct | 129 ms | 58564 KB | Output is correct |

64 | Correct | 126 ms | 57080 KB | Output is correct |

65 | Correct | 196 ms | 61644 KB | Output is correct |

66 | Correct | 193 ms | 61644 KB | Output is correct |

67 | Correct | 159 ms | 59452 KB | Output is correct |

68 | Correct | 146 ms | 59508 KB | Output is correct |

69 | Correct | 133 ms | 60552 KB | Output is correct |

70 | Correct | 143 ms | 60548 KB | Output is correct |

71 | Correct | 159 ms | 61808 KB | Output is correct |

72 | Correct | 146 ms | 61856 KB | Output is correct |

73 | Correct | 116 ms | 61592 KB | Output is correct |

74 | Correct | 103 ms | 61596 KB | Output is correct |

75 | Correct | 123 ms | 61664 KB | Output is correct |

76 | Correct | 119 ms | 61580 KB | Output is correct |

77 | Correct | 96 ms | 61576 KB | Output is correct |

78 | Correct | 136 ms | 58124 KB | Output is correct |

79 | Correct | 119 ms | 57664 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 54368 KB | Output is correct |

2 | Correct | 0 ms | 54368 KB | Output is correct |

3 | Correct | 0 ms | 54368 KB | Output is correct |

4 | Correct | 0 ms | 54368 KB | Output is correct |

5 | Correct | 0 ms | 54368 KB | Output is correct |

6 | Correct | 0 ms | 54368 KB | Output is correct |

7 | Correct | 0 ms | 54368 KB | Output is correct |

8 | Correct | 0 ms | 54368 KB | Output is correct |

9 | Correct | 0 ms | 54368 KB | Output is correct |

10 | Correct | 0 ms | 54368 KB | Output is correct |

11 | Correct | 0 ms | 54368 KB | Output is correct |

12 | Correct | 0 ms | 54368 KB | Output is correct |

13 | Correct | 0 ms | 54368 KB | Output is correct |

14 | Correct | 0 ms | 54368 KB | Output is correct |

15 | Correct | 0 ms | 54368 KB | Output is correct |

16 | Correct | 0 ms | 54368 KB | Output is correct |

17 | Correct | 0 ms | 54368 KB | Output is correct |

18 | Correct | 0 ms | 54368 KB | Output is correct |

19 | Correct | 0 ms | 54368 KB | Output is correct |

20 | Correct | 0 ms | 54368 KB | Output is correct |

21 | Correct | 0 ms | 54368 KB | Output is correct |

22 | Correct | 0 ms | 54368 KB | Output is correct |

23 | Correct | 0 ms | 54368 KB | Output is correct |

24 | Correct | 0 ms | 54368 KB | Output is correct |

25 | Correct | 0 ms | 54528 KB | Output is correct |

26 | Correct | 0 ms | 54528 KB | Output is correct |

27 | Correct | 0 ms | 54528 KB | Output is correct |

28 | Correct | 0 ms | 54528 KB | Output is correct |

29 | Correct | 0 ms | 54528 KB | Output is correct |

30 | Correct | 0 ms | 54528 KB | Output is correct |

31 | Correct | 0 ms | 54520 KB | Output is correct |

32 | Correct | 0 ms | 54528 KB | Output is correct |

33 | Correct | 0 ms | 54528 KB | Output is correct |

34 | Correct | 3 ms | 54520 KB | Output is correct |

35 | Correct | 0 ms | 54508 KB | Output is correct |

36 | Correct | 0 ms | 54508 KB | Output is correct |

37 | Correct | 0 ms | 54500 KB | Output is correct |

38 | Correct | 0 ms | 54368 KB | Output is correct |

39 | Correct | 0 ms | 54504 KB | Output is correct |

40 | Correct | 0 ms | 54508 KB | Output is correct |

41 | Correct | 0 ms | 54368 KB | Output is correct |

42 | Correct | 0 ms | 54368 KB | Output is correct |

43 | Correct | 0 ms | 54368 KB | Output is correct |

44 | Correct | 0 ms | 54368 KB | Output is correct |

45 | Correct | 119 ms | 57632 KB | Output is correct |

46 | Correct | 139 ms | 58268 KB | Output is correct |

47 | Correct | 156 ms | 57196 KB | Output is correct |

48 | Correct | 149 ms | 58252 KB | Output is correct |

49 | Correct | 109 ms | 57288 KB | Output is correct |

50 | Correct | 109 ms | 58084 KB | Output is correct |

51 | Correct | 146 ms | 58072 KB | Output is correct |

52 | Correct | 99 ms | 57524 KB | Output is correct |

53 | Correct | 103 ms | 58096 KB | Output is correct |

54 | Correct | 129 ms | 61576 KB | Output is correct |

55 | Correct | 159 ms | 59232 KB | Output is correct |

56 | Correct | 123 ms | 59232 KB | Output is correct |

57 | Correct | 79 ms | 57016 KB | Output is correct |

58 | Correct | 109 ms | 57524 KB | Output is correct |

59 | Correct | 106 ms | 57780 KB | Output is correct |

60 | Correct | 129 ms | 58548 KB | Output is correct |

61 | Correct | 126 ms | 57100 KB | Output is correct |

62 | Correct | 96 ms | 57780 KB | Output is correct |

63 | Correct | 129 ms | 58564 KB | Output is correct |

64 | Correct | 126 ms | 57080 KB | Output is correct |

65 | Correct | 196 ms | 61644 KB | Output is correct |

66 | Correct | 193 ms | 61644 KB | Output is correct |

67 | Correct | 159 ms | 59452 KB | Output is correct |

68 | Correct | 146 ms | 59508 KB | Output is correct |

69 | Correct | 133 ms | 60552 KB | Output is correct |

70 | Correct | 143 ms | 60548 KB | Output is correct |

71 | Correct | 159 ms | 61808 KB | Output is correct |

72 | Correct | 146 ms | 61856 KB | Output is correct |

73 | Correct | 116 ms | 61592 KB | Output is correct |

74 | Correct | 103 ms | 61596 KB | Output is correct |

75 | Correct | 123 ms | 61664 KB | Output is correct |

76 | Correct | 119 ms | 61580 KB | Output is correct |

77 | Correct | 96 ms | 61576 KB | Output is correct |

78 | Correct | 136 ms | 58124 KB | Output is correct |

79 | Correct | 119 ms | 57664 KB | Output is correct |

80 | Correct | 2009 ms | 90076 KB | Output is correct |

81 | Correct | 1969 ms | 89512 KB | Output is correct |

82 | Correct | 1933 ms | 87932 KB | Output is correct |

83 | Correct | 1949 ms | 89556 KB | Output is correct |

84 | Correct | 2043 ms | 90096 KB | Output is correct |

85 | Correct | 1859 ms | 87996 KB | Output is correct |

86 | Correct | 1873 ms | 89588 KB | Output is correct |

87 | Correct | 1546 ms | 79028 KB | Output is correct |

88 | Correct | 1806 ms | 87460 KB | Output is correct |

89 | Correct | 1986 ms | 121748 KB | Output is correct |

90 | Correct | 1993 ms | 98248 KB | Output is correct |

91 | Correct | 2136 ms | 98248 KB | Output is correct |

92 | Correct | 1629 ms | 74936 KB | Output is correct |

93 | Correct | 1513 ms | 79028 KB | Output is correct |

94 | Correct | 1773 ms | 83124 KB | Output is correct |

95 | Correct | 1733 ms | 87308 KB | Output is correct |

96 | Correct | 1753 ms | 87288 KB | Output is correct |

97 | Correct | 1676 ms | 87220 KB | Output is correct |

98 | Correct | 1729 ms | 87308 KB | Output is correct |

99 | Correct | 1813 ms | 87308 KB | Output is correct |

100 | Correct | 2863 ms | 121688 KB | Output is correct |

101 | Correct | 2783 ms | 121684 KB | Output is correct |

102 | Correct | 2066 ms | 102480 KB | Output is correct |

103 | Correct | 2025 ms | 102448 KB | Output is correct |

104 | Correct | 2096 ms | 110688 KB | Output is correct |

105 | Correct | 2069 ms | 110712 KB | Output is correct |

106 | Correct | 2066 ms | 125896 KB | Output is correct |

107 | Correct | 2136 ms | 125900 KB | Output is correct |

108 | Correct | 1956 ms | 121112 KB | Output is correct |

109 | Correct | 1963 ms | 121112 KB | Output is correct |

110 | Correct | 1796 ms | 121688 KB | Output is correct |

111 | Correct | 1639 ms | 121688 KB | Output is correct |

112 | Correct | 1656 ms | 121688 KB | Output is correct |

113 | Correct | 1946 ms | 87592 KB | Output is correct |

114 | Correct | 1996 ms | 89428 KB | Output is correct |