| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 125285 | 2019-07-05T04:38:30 Z | 조승현(#3064) | Arranging Tickets (JOI17_arranging_tickets) | C++14 | 5560 ms | 476 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]++;
}
int z = 150000000 / max(n, m);
for (j = 0; j < z; 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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2603 ms | 376 KB | Output is correct |
| 2 | Correct | 2568 ms | 380 KB | Output is correct |
| 3 | Correct | 2593 ms | 376 KB | Output is correct |
| 4 | Correct | 2632 ms | 348 KB | Output is correct |
| 5 | Correct | 2535 ms | 356 KB | Output is correct |
| 6 | Correct | 3414 ms | 352 KB | Output is correct |
| 7 | Correct | 3508 ms | 356 KB | Output is correct |
| 8 | Correct | 2538 ms | 376 KB | Output is correct |
| 9 | Correct | 2477 ms | 352 KB | Output is correct |
| 10 | Correct | 2501 ms | 256 KB | Output is correct |
| 11 | Correct | 3364 ms | 348 KB | Output is correct |
| 12 | Correct | 1680 ms | 256 KB | Output is correct |
| 13 | Correct | 2612 ms | 348 KB | Output is correct |
| 14 | Correct | 1629 ms | 376 KB | Output is correct |
| 15 | Correct | 2513 ms | 348 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2603 ms | 376 KB | Output is correct |
| 2 | Correct | 2568 ms | 380 KB | Output is correct |
| 3 | Correct | 2593 ms | 376 KB | Output is correct |
| 4 | Correct | 2632 ms | 348 KB | Output is correct |
| 5 | Correct | 2535 ms | 356 KB | Output is correct |
| 6 | Correct | 3414 ms | 352 KB | Output is correct |
| 7 | Correct | 3508 ms | 356 KB | Output is correct |
| 8 | Correct | 2538 ms | 376 KB | Output is correct |
| 9 | Correct | 2477 ms | 352 KB | Output is correct |
| 10 | Correct | 2501 ms | 256 KB | Output is correct |
| 11 | Correct | 3364 ms | 348 KB | Output is correct |
| 12 | Correct | 1680 ms | 256 KB | Output is correct |
| 13 | Correct | 2612 ms | 348 KB | Output is correct |
| 14 | Correct | 1629 ms | 376 KB | Output is correct |
| 15 | Correct | 2513 ms | 348 KB | Output is correct |
| 16 | Correct | 3927 ms | 356 KB | Output is correct |
| 17 | Correct | 3957 ms | 360 KB | Output is correct |
| 18 | Correct | 3177 ms | 476 KB | Output is correct |
| 19 | Correct | 4729 ms | 356 KB | Output is correct |
| 20 | Correct | 3249 ms | 352 KB | Output is correct |
| 21 | Correct | 4005 ms | 356 KB | Output is correct |
| 22 | Correct | 3973 ms | 360 KB | Output is correct |
| 23 | Correct | 2407 ms | 356 KB | Output is correct |
| 24 | Correct | 4062 ms | 256 KB | Output is correct |
| 25 | Correct | 5560 ms | 388 KB | Output is correct |
| 26 | Correct | 3101 ms | 360 KB | Output is correct |
| 27 | Correct | 3261 ms | 476 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2603 ms | 376 KB | Output is correct |
| 2 | Correct | 2568 ms | 380 KB | Output is correct |
| 3 | Correct | 2593 ms | 376 KB | Output is correct |
| 4 | Correct | 2632 ms | 348 KB | Output is correct |
| 5 | Correct | 2535 ms | 356 KB | Output is correct |
| 6 | Correct | 3414 ms | 352 KB | Output is correct |
| 7 | Correct | 3508 ms | 356 KB | Output is correct |
| 8 | Correct | 2538 ms | 376 KB | Output is correct |
| 9 | Correct | 2477 ms | 352 KB | Output is correct |
| 10 | Correct | 2501 ms | 256 KB | Output is correct |
| 11 | Correct | 3364 ms | 348 KB | Output is correct |
| 12 | Correct | 1680 ms | 256 KB | Output is correct |
| 13 | Correct | 2612 ms | 348 KB | Output is correct |
| 14 | Correct | 1629 ms | 376 KB | Output is correct |
| 15 | Correct | 2513 ms | 348 KB | Output is correct |
| 16 | Correct | 3927 ms | 356 KB | Output is correct |
| 17 | Correct | 3957 ms | 360 KB | Output is correct |
| 18 | Correct | 3177 ms | 476 KB | Output is correct |
| 19 | Correct | 4729 ms | 356 KB | Output is correct |
| 20 | Correct | 3249 ms | 352 KB | Output is correct |
| 21 | Correct | 4005 ms | 356 KB | Output is correct |
| 22 | Correct | 3973 ms | 360 KB | Output is correct |
| 23 | Correct | 2407 ms | 356 KB | Output is correct |
| 24 | Correct | 4062 ms | 256 KB | Output is correct |
| 25 | Correct | 5560 ms | 388 KB | Output is correct |
| 26 | Correct | 3101 ms | 360 KB | Output is correct |
| 27 | Correct | 3261 ms | 476 KB | Output is correct |
| 28 | Incorrect | 3864 ms | 396 KB | Output isn't correct |
| 29 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2603 ms | 376 KB | Output is correct |
| 2 | Correct | 2568 ms | 380 KB | Output is correct |
| 3 | Correct | 2593 ms | 376 KB | Output is correct |
| 4 | Correct | 2632 ms | 348 KB | Output is correct |
| 5 | Correct | 2535 ms | 356 KB | Output is correct |
| 6 | Correct | 3414 ms | 352 KB | Output is correct |
| 7 | Correct | 3508 ms | 356 KB | Output is correct |
| 8 | Correct | 2538 ms | 376 KB | Output is correct |
| 9 | Correct | 2477 ms | 352 KB | Output is correct |
| 10 | Correct | 2501 ms | 256 KB | Output is correct |
| 11 | Correct | 3364 ms | 348 KB | Output is correct |
| 12 | Correct | 1680 ms | 256 KB | Output is correct |
| 13 | Correct | 2612 ms | 348 KB | Output is correct |
| 14 | Correct | 1629 ms | 376 KB | Output is correct |
| 15 | Correct | 2513 ms | 348 KB | Output is correct |
| 16 | Correct | 3927 ms | 356 KB | Output is correct |
| 17 | Correct | 3957 ms | 360 KB | Output is correct |
| 18 | Correct | 3177 ms | 476 KB | Output is correct |
| 19 | Correct | 4729 ms | 356 KB | Output is correct |
| 20 | Correct | 3249 ms | 352 KB | Output is correct |
| 21 | Correct | 4005 ms | 356 KB | Output is correct |
| 22 | Correct | 3973 ms | 360 KB | Output is correct |
| 23 | Correct | 2407 ms | 356 KB | Output is correct |
| 24 | Correct | 4062 ms | 256 KB | Output is correct |
| 25 | Correct | 5560 ms | 388 KB | Output is correct |
| 26 | Correct | 3101 ms | 360 KB | Output is correct |
| 27 | Correct | 3261 ms | 476 KB | Output is correct |
| 28 | Incorrect | 3864 ms | 396 KB | Output isn't correct |
| 29 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2603 ms | 376 KB | Output is correct |
| 2 | Correct | 2568 ms | 380 KB | Output is correct |
| 3 | Correct | 2593 ms | 376 KB | Output is correct |
| 4 | Correct | 2632 ms | 348 KB | Output is correct |
| 5 | Correct | 2535 ms | 356 KB | Output is correct |
| 6 | Correct | 3414 ms | 352 KB | Output is correct |
| 7 | Correct | 3508 ms | 356 KB | Output is correct |
| 8 | Correct | 2538 ms | 376 KB | Output is correct |
| 9 | Correct | 2477 ms | 352 KB | Output is correct |
| 10 | Correct | 2501 ms | 256 KB | Output is correct |
| 11 | Correct | 3364 ms | 348 KB | Output is correct |
| 12 | Correct | 1680 ms | 256 KB | Output is correct |
| 13 | Correct | 2612 ms | 348 KB | Output is correct |
| 14 | Correct | 1629 ms | 376 KB | Output is correct |
| 15 | Correct | 2513 ms | 348 KB | Output is correct |
| 16 | Correct | 3927 ms | 356 KB | Output is correct |
| 17 | Correct | 3957 ms | 360 KB | Output is correct |
| 18 | Correct | 3177 ms | 476 KB | Output is correct |
| 19 | Correct | 4729 ms | 356 KB | Output is correct |
| 20 | Correct | 3249 ms | 352 KB | Output is correct |
| 21 | Correct | 4005 ms | 356 KB | Output is correct |
| 22 | Correct | 3973 ms | 360 KB | Output is correct |
| 23 | Correct | 2407 ms | 356 KB | Output is correct |
| 24 | Correct | 4062 ms | 256 KB | Output is correct |
| 25 | Correct | 5560 ms | 388 KB | Output is correct |
| 26 | Correct | 3101 ms | 360 KB | Output is correct |
| 27 | Correct | 3261 ms | 476 KB | Output is correct |
| 28 | Incorrect | 3864 ms | 396 KB | Output isn't correct |
| 29 | Halted | 0 ms | 0 KB | - |