# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
125282 | 2019-07-05T04:09:45 Z | 조승현(#3064) | Arranging Tickets (JOI17_arranging_tickets) | C++14 | 1865 ms | 504 KB |
#include<cstdio> #include<algorithm> using namespace std; int n, m, C[3010], S[3010], CK[3010]; struct point { int a, b; }w[3010]; bool Pos(int K) { int i, j; for (i = 1; i <= n; i++)C[i] = 0; for (i = 1; i <= m; i++) { CK[i] = 0; for (j = w[i].a; j < w[i].b; j++)C[j]++; } for (j = 0; j < 50000000 / max(n, m); j++) { int Mx = 0, ss = 0; S[0] = 0; for (i = 1; i <= n; i++) { S[i] = S[i - 1] + (C[i] >= K); ss += (C[i] > K); } if (ss == 0)return true; int MM = -1, pv = -1; for (i = 1; i <= m; i++) { int t = S[w[i].b - 1] - S[w[i].a - 1]; if (CK[i])t = S[n] - t; if (MM < t)MM = t, pv = i; } for (i = 1; i <= n; i++) { if ((CK[pv] == 0) == (w[pv].a <= i && i < w[pv].b)) C[i]--; else C[i]++; } CK[pv] ^= 1; } return false; } int main() { int i, j; scanf("%d%d", &n, &m); if (n > 3000 || m > 3000)return 0; for (i = 1; i <= m; i++) { int t; scanf("%d%d%d", &w[i].a, &w[i].b, &t); if (w[i].a > w[i].b)swap(w[i].a, w[i].b); } int res = 1e9; int b = 1, e = m, mid, r; while (b <= e) { mid = (b + e) >> 1; if (Pos(mid)) { r = mid; e = mid - 1; } else b = mid + 1; } printf("%d\n", r); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 866 ms | 376 KB | Output is correct |
2 | Correct | 849 ms | 376 KB | Output is correct |
3 | Correct | 866 ms | 476 KB | Output is correct |
4 | Correct | 878 ms | 376 KB | Output is correct |
5 | Correct | 844 ms | 376 KB | Output is correct |
6 | Correct | 1121 ms | 376 KB | Output is correct |
7 | Correct | 1168 ms | 376 KB | Output is correct |
8 | Correct | 847 ms | 376 KB | Output is correct |
9 | Correct | 814 ms | 376 KB | Output is correct |
10 | Correct | 836 ms | 504 KB | Output is correct |
11 | Correct | 1120 ms | 356 KB | Output is correct |
12 | Correct | 560 ms | 356 KB | Output is correct |
13 | Correct | 868 ms | 256 KB | Output is correct |
14 | Correct | 543 ms | 376 KB | Output is correct |
15 | Correct | 840 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 866 ms | 376 KB | Output is correct |
2 | Correct | 849 ms | 376 KB | Output is correct |
3 | Correct | 866 ms | 476 KB | Output is correct |
4 | Correct | 878 ms | 376 KB | Output is correct |
5 | Correct | 844 ms | 376 KB | Output is correct |
6 | Correct | 1121 ms | 376 KB | Output is correct |
7 | Correct | 1168 ms | 376 KB | Output is correct |
8 | Correct | 847 ms | 376 KB | Output is correct |
9 | Correct | 814 ms | 376 KB | Output is correct |
10 | Correct | 836 ms | 504 KB | Output is correct |
11 | Correct | 1120 ms | 356 KB | Output is correct |
12 | Correct | 560 ms | 356 KB | Output is correct |
13 | Correct | 868 ms | 256 KB | Output is correct |
14 | Correct | 543 ms | 376 KB | Output is correct |
15 | Correct | 840 ms | 376 KB | Output is correct |
16 | Correct | 1309 ms | 376 KB | Output is correct |
17 | Correct | 1319 ms | 376 KB | Output is correct |
18 | Correct | 1057 ms | 256 KB | Output is correct |
19 | Correct | 1574 ms | 376 KB | Output is correct |
20 | Correct | 1089 ms | 376 KB | Output is correct |
21 | Correct | 1334 ms | 376 KB | Output is correct |
22 | Correct | 1328 ms | 252 KB | Output is correct |
23 | Correct | 802 ms | 504 KB | Output is correct |
24 | Correct | 1349 ms | 360 KB | Output is correct |
25 | Correct | 1865 ms | 356 KB | Output is correct |
26 | Correct | 1038 ms | 376 KB | Output is correct |
27 | Correct | 1111 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 866 ms | 376 KB | Output is correct |
2 | Correct | 849 ms | 376 KB | Output is correct |
3 | Correct | 866 ms | 476 KB | Output is correct |
4 | Correct | 878 ms | 376 KB | Output is correct |
5 | Correct | 844 ms | 376 KB | Output is correct |
6 | Correct | 1121 ms | 376 KB | Output is correct |
7 | Correct | 1168 ms | 376 KB | Output is correct |
8 | Correct | 847 ms | 376 KB | Output is correct |
9 | Correct | 814 ms | 376 KB | Output is correct |
10 | Correct | 836 ms | 504 KB | Output is correct |
11 | Correct | 1120 ms | 356 KB | Output is correct |
12 | Correct | 560 ms | 356 KB | Output is correct |
13 | Correct | 868 ms | 256 KB | Output is correct |
14 | Correct | 543 ms | 376 KB | Output is correct |
15 | Correct | 840 ms | 376 KB | Output is correct |
16 | Correct | 1309 ms | 376 KB | Output is correct |
17 | Correct | 1319 ms | 376 KB | Output is correct |
18 | Correct | 1057 ms | 256 KB | Output is correct |
19 | Correct | 1574 ms | 376 KB | Output is correct |
20 | Correct | 1089 ms | 376 KB | Output is correct |
21 | Correct | 1334 ms | 376 KB | Output is correct |
22 | Correct | 1328 ms | 252 KB | Output is correct |
23 | Correct | 802 ms | 504 KB | Output is correct |
24 | Correct | 1349 ms | 360 KB | Output is correct |
25 | Correct | 1865 ms | 356 KB | Output is correct |
26 | Correct | 1038 ms | 376 KB | Output is correct |
27 | Correct | 1111 ms | 376 KB | Output is correct |
28 | Incorrect | 1393 ms | 436 KB | Output isn't correct |
29 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 866 ms | 376 KB | Output is correct |
2 | Correct | 849 ms | 376 KB | Output is correct |
3 | Correct | 866 ms | 476 KB | Output is correct |
4 | Correct | 878 ms | 376 KB | Output is correct |
5 | Correct | 844 ms | 376 KB | Output is correct |
6 | Correct | 1121 ms | 376 KB | Output is correct |
7 | Correct | 1168 ms | 376 KB | Output is correct |
8 | Correct | 847 ms | 376 KB | Output is correct |
9 | Correct | 814 ms | 376 KB | Output is correct |
10 | Correct | 836 ms | 504 KB | Output is correct |
11 | Correct | 1120 ms | 356 KB | Output is correct |
12 | Correct | 560 ms | 356 KB | Output is correct |
13 | Correct | 868 ms | 256 KB | Output is correct |
14 | Correct | 543 ms | 376 KB | Output is correct |
15 | Correct | 840 ms | 376 KB | Output is correct |
16 | Correct | 1309 ms | 376 KB | Output is correct |
17 | Correct | 1319 ms | 376 KB | Output is correct |
18 | Correct | 1057 ms | 256 KB | Output is correct |
19 | Correct | 1574 ms | 376 KB | Output is correct |
20 | Correct | 1089 ms | 376 KB | Output is correct |
21 | Correct | 1334 ms | 376 KB | Output is correct |
22 | Correct | 1328 ms | 252 KB | Output is correct |
23 | Correct | 802 ms | 504 KB | Output is correct |
24 | Correct | 1349 ms | 360 KB | Output is correct |
25 | Correct | 1865 ms | 356 KB | Output is correct |
26 | Correct | 1038 ms | 376 KB | Output is correct |
27 | Correct | 1111 ms | 376 KB | Output is correct |
28 | Incorrect | 1393 ms | 436 KB | Output isn't correct |
29 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 866 ms | 376 KB | Output is correct |
2 | Correct | 849 ms | 376 KB | Output is correct |
3 | Correct | 866 ms | 476 KB | Output is correct |
4 | Correct | 878 ms | 376 KB | Output is correct |
5 | Correct | 844 ms | 376 KB | Output is correct |
6 | Correct | 1121 ms | 376 KB | Output is correct |
7 | Correct | 1168 ms | 376 KB | Output is correct |
8 | Correct | 847 ms | 376 KB | Output is correct |
9 | Correct | 814 ms | 376 KB | Output is correct |
10 | Correct | 836 ms | 504 KB | Output is correct |
11 | Correct | 1120 ms | 356 KB | Output is correct |
12 | Correct | 560 ms | 356 KB | Output is correct |
13 | Correct | 868 ms | 256 KB | Output is correct |
14 | Correct | 543 ms | 376 KB | Output is correct |
15 | Correct | 840 ms | 376 KB | Output is correct |
16 | Correct | 1309 ms | 376 KB | Output is correct |
17 | Correct | 1319 ms | 376 KB | Output is correct |
18 | Correct | 1057 ms | 256 KB | Output is correct |
19 | Correct | 1574 ms | 376 KB | Output is correct |
20 | Correct | 1089 ms | 376 KB | Output is correct |
21 | Correct | 1334 ms | 376 KB | Output is correct |
22 | Correct | 1328 ms | 252 KB | Output is correct |
23 | Correct | 802 ms | 504 KB | Output is correct |
24 | Correct | 1349 ms | 360 KB | Output is correct |
25 | Correct | 1865 ms | 356 KB | Output is correct |
26 | Correct | 1038 ms | 376 KB | Output is correct |
27 | Correct | 1111 ms | 376 KB | Output is correct |
28 | Incorrect | 1393 ms | 436 KB | Output isn't correct |
29 | Halted | 0 ms | 0 KB | - |