# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
31149 | 2017-08-11T14:52:27 Z | gs14004 | Arranging Tickets (JOI17_arranging_tickets) | C++14 | 879 ms | 4768 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], b[200005]; struct seg{ int tree[3005]; void init(){ memset(tree, 0, sizeof(tree)); } void add(int x, int v){ while(x <= n){ tree[x] += v; x += x & -x; } } int query(int x){ int ret = 0; while(x){ ret += tree[x]; x -= x & -x; } return ret; } }seg; int solve(int x){ int pnt = 0; priority_queue<int> pq; seg.init(); for(int i=1; i<n; i++) b[i] = max(dx[i] - x, 0); for(int i=1; i<n; i++){ seg.add(i, b[i] - b[i-1]); } for(int i=1; i<n; i++){ while(pnt < m && a[pnt].s <= i){ pq.push(a[pnt++].e); } while(seg.query(i) > 0 && !pq.empty()){ auto l = pq.top(); pq.pop(); if(l <= i) continue; seg.add(i, -2); seg.add(l, 2); x++; } if(seg.query(i) > 0) return 1e9; } return x; } 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; }); 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 ans = 1e9; for(int i=-m; i<=m; i++){ ans = min(ans, solve(i)); } printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4768 KB | Output is correct |
2 | Correct | 0 ms | 4768 KB | Output is correct |
3 | Correct | 0 ms | 4768 KB | Output is correct |
4 | Correct | 0 ms | 4768 KB | Output is correct |
5 | Correct | 0 ms | 4768 KB | Output is correct |
6 | Correct | 0 ms | 4768 KB | Output is correct |
7 | Correct | 0 ms | 4768 KB | Output is correct |
8 | Correct | 0 ms | 4768 KB | Output is correct |
9 | Correct | 0 ms | 4768 KB | Output is correct |
10 | Correct | 0 ms | 4768 KB | Output is correct |
11 | Correct | 0 ms | 4768 KB | Output is correct |
12 | Correct | 0 ms | 4768 KB | Output is correct |
13 | Correct | 0 ms | 4768 KB | Output is correct |
14 | Correct | 0 ms | 4768 KB | Output is correct |
15 | Correct | 0 ms | 4768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4768 KB | Output is correct |
2 | Correct | 0 ms | 4768 KB | Output is correct |
3 | Correct | 0 ms | 4768 KB | Output is correct |
4 | Correct | 0 ms | 4768 KB | Output is correct |
5 | Correct | 0 ms | 4768 KB | Output is correct |
6 | Correct | 0 ms | 4768 KB | Output is correct |
7 | Correct | 0 ms | 4768 KB | Output is correct |
8 | Correct | 0 ms | 4768 KB | Output is correct |
9 | Correct | 0 ms | 4768 KB | Output is correct |
10 | Correct | 0 ms | 4768 KB | Output is correct |
11 | Correct | 0 ms | 4768 KB | Output is correct |
12 | Correct | 0 ms | 4768 KB | Output is correct |
13 | Correct | 0 ms | 4768 KB | Output is correct |
14 | Correct | 0 ms | 4768 KB | Output is correct |
15 | Correct | 0 ms | 4768 KB | Output is correct |
16 | Correct | 6 ms | 4768 KB | Output is correct |
17 | Correct | 6 ms | 4768 KB | Output is correct |
18 | Correct | 6 ms | 4768 KB | Output is correct |
19 | Correct | 6 ms | 4768 KB | Output is correct |
20 | Correct | 3 ms | 4768 KB | Output is correct |
21 | Correct | 3 ms | 4768 KB | Output is correct |
22 | Correct | 3 ms | 4768 KB | Output is correct |
23 | Correct | 9 ms | 4768 KB | Output is correct |
24 | Correct | 3 ms | 4768 KB | Output is correct |
25 | Correct | 3 ms | 4768 KB | Output is correct |
26 | Correct | 6 ms | 4768 KB | Output is correct |
27 | Correct | 3 ms | 4768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4768 KB | Output is correct |
2 | Correct | 0 ms | 4768 KB | Output is correct |
3 | Correct | 0 ms | 4768 KB | Output is correct |
4 | Correct | 0 ms | 4768 KB | Output is correct |
5 | Correct | 0 ms | 4768 KB | Output is correct |
6 | Correct | 0 ms | 4768 KB | Output is correct |
7 | Correct | 0 ms | 4768 KB | Output is correct |
8 | Correct | 0 ms | 4768 KB | Output is correct |
9 | Correct | 0 ms | 4768 KB | Output is correct |
10 | Correct | 0 ms | 4768 KB | Output is correct |
11 | Correct | 0 ms | 4768 KB | Output is correct |
12 | Correct | 0 ms | 4768 KB | Output is correct |
13 | Correct | 0 ms | 4768 KB | Output is correct |
14 | Correct | 0 ms | 4768 KB | Output is correct |
15 | Correct | 0 ms | 4768 KB | Output is correct |
16 | Correct | 6 ms | 4768 KB | Output is correct |
17 | Correct | 6 ms | 4768 KB | Output is correct |
18 | Correct | 6 ms | 4768 KB | Output is correct |
19 | Correct | 6 ms | 4768 KB | Output is correct |
20 | Correct | 3 ms | 4768 KB | Output is correct |
21 | Correct | 3 ms | 4768 KB | Output is correct |
22 | Correct | 3 ms | 4768 KB | Output is correct |
23 | Correct | 9 ms | 4768 KB | Output is correct |
24 | Correct | 3 ms | 4768 KB | Output is correct |
25 | Correct | 3 ms | 4768 KB | Output is correct |
26 | Correct | 6 ms | 4768 KB | Output is correct |
27 | Correct | 3 ms | 4768 KB | Output is correct |
28 | Correct | 879 ms | 4768 KB | Output is correct |
29 | Correct | 829 ms | 4768 KB | Output is correct |
30 | Correct | 823 ms | 4768 KB | Output is correct |
31 | Correct | 826 ms | 4768 KB | Output is correct |
32 | Correct | 843 ms | 4768 KB | Output is correct |
33 | Correct | 783 ms | 4768 KB | Output is correct |
34 | Incorrect | 809 ms | 4768 KB | Output isn't correct |
35 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4768 KB | Output is correct |
2 | Correct | 0 ms | 4768 KB | Output is correct |
3 | Correct | 0 ms | 4768 KB | Output is correct |
4 | Correct | 0 ms | 4768 KB | Output is correct |
5 | Correct | 0 ms | 4768 KB | Output is correct |
6 | Correct | 0 ms | 4768 KB | Output is correct |
7 | Correct | 0 ms | 4768 KB | Output is correct |
8 | Correct | 0 ms | 4768 KB | Output is correct |
9 | Correct | 0 ms | 4768 KB | Output is correct |
10 | Correct | 0 ms | 4768 KB | Output is correct |
11 | Correct | 0 ms | 4768 KB | Output is correct |
12 | Correct | 0 ms | 4768 KB | Output is correct |
13 | Correct | 0 ms | 4768 KB | Output is correct |
14 | Correct | 0 ms | 4768 KB | Output is correct |
15 | Correct | 0 ms | 4768 KB | Output is correct |
16 | Correct | 6 ms | 4768 KB | Output is correct |
17 | Correct | 6 ms | 4768 KB | Output is correct |
18 | Correct | 6 ms | 4768 KB | Output is correct |
19 | Correct | 6 ms | 4768 KB | Output is correct |
20 | Correct | 3 ms | 4768 KB | Output is correct |
21 | Correct | 3 ms | 4768 KB | Output is correct |
22 | Correct | 3 ms | 4768 KB | Output is correct |
23 | Correct | 9 ms | 4768 KB | Output is correct |
24 | Correct | 3 ms | 4768 KB | Output is correct |
25 | Correct | 3 ms | 4768 KB | Output is correct |
26 | Correct | 6 ms | 4768 KB | Output is correct |
27 | Correct | 3 ms | 4768 KB | Output is correct |
28 | Correct | 879 ms | 4768 KB | Output is correct |
29 | Correct | 829 ms | 4768 KB | Output is correct |
30 | Correct | 823 ms | 4768 KB | Output is correct |
31 | Correct | 826 ms | 4768 KB | Output is correct |
32 | Correct | 843 ms | 4768 KB | Output is correct |
33 | Correct | 783 ms | 4768 KB | Output is correct |
34 | Incorrect | 809 ms | 4768 KB | Output isn't correct |
35 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4768 KB | Output is correct |
2 | Correct | 0 ms | 4768 KB | Output is correct |
3 | Correct | 0 ms | 4768 KB | Output is correct |
4 | Correct | 0 ms | 4768 KB | Output is correct |
5 | Correct | 0 ms | 4768 KB | Output is correct |
6 | Correct | 0 ms | 4768 KB | Output is correct |
7 | Correct | 0 ms | 4768 KB | Output is correct |
8 | Correct | 0 ms | 4768 KB | Output is correct |
9 | Correct | 0 ms | 4768 KB | Output is correct |
10 | Correct | 0 ms | 4768 KB | Output is correct |
11 | Correct | 0 ms | 4768 KB | Output is correct |
12 | Correct | 0 ms | 4768 KB | Output is correct |
13 | Correct | 0 ms | 4768 KB | Output is correct |
14 | Correct | 0 ms | 4768 KB | Output is correct |
15 | Correct | 0 ms | 4768 KB | Output is correct |
16 | Correct | 6 ms | 4768 KB | Output is correct |
17 | Correct | 6 ms | 4768 KB | Output is correct |
18 | Correct | 6 ms | 4768 KB | Output is correct |
19 | Correct | 6 ms | 4768 KB | Output is correct |
20 | Correct | 3 ms | 4768 KB | Output is correct |
21 | Correct | 3 ms | 4768 KB | Output is correct |
22 | Correct | 3 ms | 4768 KB | Output is correct |
23 | Correct | 9 ms | 4768 KB | Output is correct |
24 | Correct | 3 ms | 4768 KB | Output is correct |
25 | Correct | 3 ms | 4768 KB | Output is correct |
26 | Correct | 6 ms | 4768 KB | Output is correct |
27 | Correct | 3 ms | 4768 KB | Output is correct |
28 | Correct | 879 ms | 4768 KB | Output is correct |
29 | Correct | 829 ms | 4768 KB | Output is correct |
30 | Correct | 823 ms | 4768 KB | Output is correct |
31 | Correct | 826 ms | 4768 KB | Output is correct |
32 | Correct | 843 ms | 4768 KB | Output is correct |
33 | Correct | 783 ms | 4768 KB | Output is correct |
34 | Incorrect | 809 ms | 4768 KB | Output isn't correct |
35 | Halted | 0 ms | 0 KB | - |