# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
29001 | 2017-07-18T05:17:30 Z | 구사과(#1234) | Arranging Tickets (JOI17_arranging_tickets) | C++14 | 6000 ms | 3976 KB |
#include <bits/stdc++.h> using namespace std; typedef long long lint; typedef long double llf; typedef pair<int, int> pi; struct intv{ int s, e, x; }a[100005]; int n, m; int dx[200005]; bool solve(int r, int c){ memset(dx, 0, sizeof(dx)); for(int i=0; i<m; i++){ dx[a[i].s]++; dx[a[i].e]--; } for(int i=1; i<=n; i++) dx[i] += dx[i-1]; int pnt = 0; priority_queue<int> pq; for(int i=1; i<n; i++){ dx[i] = max(dx[i] - (c - r) + 1, 0) / 2; } for(int i=1; i<n; i++){ while(pnt < m && a[pnt].s <= i){ pq.push(a[pnt++].e); } while(dx[i] > 0 && !pq.empty()){ auto l = pq.top(); pq.pop(); if(l <= i) continue; for(int j=i; j<l; j++) dx[j] = max(dx[j] - 1, 0); r--; } if(dx[i] > 0) return 0; } return r >= 0; } int main(){ scanf("%d %d",&n,&m); for(int i=0; i<m; i++){ scanf("%d %d %d",&a[i].s,&a[i].e,&a[i].x); assert(a[i].x == 1); if(a[i].s > a[i].e) swap(a[i].s, a[i].e); } sort(a, a+m, [&](const intv &a, const intv &b){ return a.s < b.s; }); int ans = 1e9; for(int i=0; i<=m; i++){ int st = 0, ed = n; while(st != ed){ int m = (st+ed)/2; if(solve(i, m)) ed = m; else st = m+1; } ans = min(ans, st); } printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 3976 KB | Output is correct |
2 | Correct | 3 ms | 3976 KB | Output is correct |
3 | Correct | 3 ms | 3976 KB | Output is correct |
4 | Correct | 3 ms | 3976 KB | Output is correct |
5 | Correct | 3 ms | 3976 KB | Output is correct |
6 | Correct | 3 ms | 3976 KB | Output is correct |
7 | Correct | 3 ms | 3976 KB | Output is correct |
8 | Correct | 3 ms | 3976 KB | Output is correct |
9 | Correct | 3 ms | 3976 KB | Output is correct |
10 | Correct | 3 ms | 3976 KB | Output is correct |
11 | Correct | 3 ms | 3976 KB | Output is correct |
12 | Correct | 3 ms | 3976 KB | Output is correct |
13 | Correct | 3 ms | 3976 KB | Output is correct |
14 | Correct | 3 ms | 3976 KB | Output is correct |
15 | Correct | 3 ms | 3976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 3976 KB | Output is correct |
2 | Correct | 3 ms | 3976 KB | Output is correct |
3 | Correct | 3 ms | 3976 KB | Output is correct |
4 | Correct | 3 ms | 3976 KB | Output is correct |
5 | Correct | 3 ms | 3976 KB | Output is correct |
6 | Correct | 3 ms | 3976 KB | Output is correct |
7 | Correct | 3 ms | 3976 KB | Output is correct |
8 | Correct | 3 ms | 3976 KB | Output is correct |
9 | Correct | 3 ms | 3976 KB | Output is correct |
10 | Correct | 3 ms | 3976 KB | Output is correct |
11 | Correct | 3 ms | 3976 KB | Output is correct |
12 | Correct | 3 ms | 3976 KB | Output is correct |
13 | Correct | 3 ms | 3976 KB | Output is correct |
14 | Correct | 3 ms | 3976 KB | Output is correct |
15 | Correct | 3 ms | 3976 KB | Output is correct |
16 | Correct | 156 ms | 3976 KB | Output is correct |
17 | Correct | 156 ms | 3976 KB | Output is correct |
18 | Correct | 169 ms | 3976 KB | Output is correct |
19 | Correct | 176 ms | 3976 KB | Output is correct |
20 | Correct | 179 ms | 3976 KB | Output is correct |
21 | Correct | 153 ms | 3976 KB | Output is correct |
22 | Correct | 166 ms | 3976 KB | Output is correct |
23 | Correct | 163 ms | 3976 KB | Output is correct |
24 | Correct | 156 ms | 3976 KB | Output is correct |
25 | Correct | 146 ms | 3976 KB | Output is correct |
26 | Correct | 163 ms | 3976 KB | Output is correct |
27 | Correct | 159 ms | 3976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 3976 KB | Output is correct |
2 | Correct | 3 ms | 3976 KB | Output is correct |
3 | Correct | 3 ms | 3976 KB | Output is correct |
4 | Correct | 3 ms | 3976 KB | Output is correct |
5 | Correct | 3 ms | 3976 KB | Output is correct |
6 | Correct | 3 ms | 3976 KB | Output is correct |
7 | Correct | 3 ms | 3976 KB | Output is correct |
8 | Correct | 3 ms | 3976 KB | Output is correct |
9 | Correct | 3 ms | 3976 KB | Output is correct |
10 | Correct | 3 ms | 3976 KB | Output is correct |
11 | Correct | 3 ms | 3976 KB | Output is correct |
12 | Correct | 3 ms | 3976 KB | Output is correct |
13 | Correct | 3 ms | 3976 KB | Output is correct |
14 | Correct | 3 ms | 3976 KB | Output is correct |
15 | Correct | 3 ms | 3976 KB | Output is correct |
16 | Correct | 156 ms | 3976 KB | Output is correct |
17 | Correct | 156 ms | 3976 KB | Output is correct |
18 | Correct | 169 ms | 3976 KB | Output is correct |
19 | Correct | 176 ms | 3976 KB | Output is correct |
20 | Correct | 179 ms | 3976 KB | Output is correct |
21 | Correct | 153 ms | 3976 KB | Output is correct |
22 | Correct | 166 ms | 3976 KB | Output is correct |
23 | Correct | 163 ms | 3976 KB | Output is correct |
24 | Correct | 156 ms | 3976 KB | Output is correct |
25 | Correct | 146 ms | 3976 KB | Output is correct |
26 | Correct | 163 ms | 3976 KB | Output is correct |
27 | Correct | 159 ms | 3976 KB | Output is correct |
28 | Execution timed out | 6000 ms | 3976 KB | Execution timed out |
29 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 3976 KB | Output is correct |
2 | Correct | 3 ms | 3976 KB | Output is correct |
3 | Correct | 3 ms | 3976 KB | Output is correct |
4 | Correct | 3 ms | 3976 KB | Output is correct |
5 | Correct | 3 ms | 3976 KB | Output is correct |
6 | Correct | 3 ms | 3976 KB | Output is correct |
7 | Correct | 3 ms | 3976 KB | Output is correct |
8 | Correct | 3 ms | 3976 KB | Output is correct |
9 | Correct | 3 ms | 3976 KB | Output is correct |
10 | Correct | 3 ms | 3976 KB | Output is correct |
11 | Correct | 3 ms | 3976 KB | Output is correct |
12 | Correct | 3 ms | 3976 KB | Output is correct |
13 | Correct | 3 ms | 3976 KB | Output is correct |
14 | Correct | 3 ms | 3976 KB | Output is correct |
15 | Correct | 3 ms | 3976 KB | Output is correct |
16 | Correct | 156 ms | 3976 KB | Output is correct |
17 | Correct | 156 ms | 3976 KB | Output is correct |
18 | Correct | 169 ms | 3976 KB | Output is correct |
19 | Correct | 176 ms | 3976 KB | Output is correct |
20 | Correct | 179 ms | 3976 KB | Output is correct |
21 | Correct | 153 ms | 3976 KB | Output is correct |
22 | Correct | 166 ms | 3976 KB | Output is correct |
23 | Correct | 163 ms | 3976 KB | Output is correct |
24 | Correct | 156 ms | 3976 KB | Output is correct |
25 | Correct | 146 ms | 3976 KB | Output is correct |
26 | Correct | 163 ms | 3976 KB | Output is correct |
27 | Correct | 159 ms | 3976 KB | Output is correct |
28 | Execution timed out | 6000 ms | 3976 KB | Execution timed out |
29 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 3976 KB | Output is correct |
2 | Correct | 3 ms | 3976 KB | Output is correct |
3 | Correct | 3 ms | 3976 KB | Output is correct |
4 | Correct | 3 ms | 3976 KB | Output is correct |
5 | Correct | 3 ms | 3976 KB | Output is correct |
6 | Correct | 3 ms | 3976 KB | Output is correct |
7 | Correct | 3 ms | 3976 KB | Output is correct |
8 | Correct | 3 ms | 3976 KB | Output is correct |
9 | Correct | 3 ms | 3976 KB | Output is correct |
10 | Correct | 3 ms | 3976 KB | Output is correct |
11 | Correct | 3 ms | 3976 KB | Output is correct |
12 | Correct | 3 ms | 3976 KB | Output is correct |
13 | Correct | 3 ms | 3976 KB | Output is correct |
14 | Correct | 3 ms | 3976 KB | Output is correct |
15 | Correct | 3 ms | 3976 KB | Output is correct |
16 | Correct | 156 ms | 3976 KB | Output is correct |
17 | Correct | 156 ms | 3976 KB | Output is correct |
18 | Correct | 169 ms | 3976 KB | Output is correct |
19 | Correct | 176 ms | 3976 KB | Output is correct |
20 | Correct | 179 ms | 3976 KB | Output is correct |
21 | Correct | 153 ms | 3976 KB | Output is correct |
22 | Correct | 166 ms | 3976 KB | Output is correct |
23 | Correct | 163 ms | 3976 KB | Output is correct |
24 | Correct | 156 ms | 3976 KB | Output is correct |
25 | Correct | 146 ms | 3976 KB | Output is correct |
26 | Correct | 163 ms | 3976 KB | Output is correct |
27 | Correct | 159 ms | 3976 KB | Output is correct |
28 | Execution timed out | 6000 ms | 3976 KB | Execution timed out |
29 | Halted | 0 ms | 0 KB | - |