# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
587535 | 2022-07-02T05:03:06 Z | wenqi | 팀들 (IOI15_teams) | C++17 | 4000 ms | 366868 KB |
#include "teams.h" #include <bits/extc++.h> using namespace std; struct Node *nodes; int lol = 0; struct Node { int l, r; Node *lc, *rc; int sum; Node() {} Node(int l, int r) : l(l), r(r), lc(0), rc(0), sum(0) { if (l != r) { int m = (l + r) / 2; lc = nodes + lol++; rc = nodes + lol++; *lc = Node(l, m); *rc = Node(m + 1, r); } } Node *update(int p) { if (p < l or p > r) return this; Node *n = nodes + lol++; n->l = l, n->r = r; if (l == r) { n->sum = sum + 1; return n; } n->lc = lc->update(p); n->rc = rc->update(p); n->sum = n->lc->sum + n->rc->sum; return n; } int query(int ql, int qr) { if (qr < l or ql > r) return 0; if (ql <= l and qr >= r) return sum; return lc->query(ql, qr) + rc->query(ql, qr); } }; Node *roots[500069]; int N; void init(int N, int A[], int B[]) { ::N = N; nodes = new Node[50000069]; Node *root = new Node(1, N); vector<pair<int, int>> ppl; for (int i = 0; i < N; i++) ppl.push_back({B[i], A[i]}); sort(ppl.begin(), ppl.end()); roots[0] = root; for (auto [y, x] : ppl) roots[y] = root = root->update(x); for (int i = 1; i <= N; i++) if (not roots[i]) roots[i] = roots[i - 1]; } int can(int M, int K[]) { vector<int> groups(K, K + M); sort(groups.begin(), groups.end()); vector<tuple<int, int, int, int>> st; for (int sz : groups) { int hate = 0; while (not st.empty()) { auto [p, dep, more, s] = st.back(); if (sz > dep) { st.pop_back(); continue; } if (roots[dep - 1]->query(p + 1, sz) - roots[sz - 1]->query(p + 1, sz) - hate < sz) { st.pop_back(); hate += roots[dep]->query(s, p) - roots[sz - 1]->query(s, p) - more; } else break; } int a = sz; int L = st.empty() ? N : get<1>(st.back()); int b = L + 2; int start = st.empty() ? 1 : (get<0>(st.back()) + 1); while (b - a > 1) { int m = (a + b) / 2; if (roots[m - 1]->query(start, sz) - roots[sz - 1]->query(start, sz) - hate >= sz) b = m; else a = m; } if (a == L + 1) return 0; int G = roots[a]->query(start, sz) - roots[sz - 1]->query(start, sz) - hate - sz; st.push_back({sz, a, G, start}); } return 1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 304 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 2 ms | 312 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 1 ms | 340 KB | Output is correct |
17 | Correct | 1 ms | 308 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 312 KB | Output is correct |
21 | Correct | 1 ms | 340 KB | Output is correct |
22 | Correct | 1 ms | 212 KB | Output is correct |
23 | Correct | 1 ms | 212 KB | Output is correct |
24 | Correct | 1 ms | 212 KB | Output is correct |
25 | Correct | 1 ms | 212 KB | Output is correct |
26 | Correct | 1 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 91 ms | 65580 KB | Output is correct |
2 | Correct | 94 ms | 65472 KB | Output is correct |
3 | Correct | 89 ms | 65496 KB | Output is correct |
4 | Correct | 94 ms | 65728 KB | Output is correct |
5 | Correct | 51 ms | 65216 KB | Output is correct |
6 | Correct | 47 ms | 65156 KB | Output is correct |
7 | Correct | 47 ms | 65128 KB | Output is correct |
8 | Correct | 44 ms | 65132 KB | Output is correct |
9 | Correct | 133 ms | 66236 KB | Output is correct |
10 | Correct | 86 ms | 65868 KB | Output is correct |
11 | Correct | 46 ms | 65928 KB | Output is correct |
12 | Correct | 42 ms | 65984 KB | Output is correct |
13 | Correct | 52 ms | 65688 KB | Output is correct |
14 | Correct | 51 ms | 66036 KB | Output is correct |
15 | Correct | 77 ms | 65444 KB | Output is correct |
16 | Correct | 79 ms | 65532 KB | Output is correct |
17 | Correct | 45 ms | 66364 KB | Output is correct |
18 | Correct | 46 ms | 66384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 105 ms | 65724 KB | Output is correct |
2 | Correct | 96 ms | 65736 KB | Output is correct |
3 | Correct | 1024 ms | 68728 KB | Output is correct |
4 | Correct | 88 ms | 65728 KB | Output is correct |
5 | Correct | 293 ms | 65400 KB | Output is correct |
6 | Correct | 272 ms | 65356 KB | Output is correct |
7 | Correct | 50 ms | 65392 KB | Output is correct |
8 | Correct | 211 ms | 65344 KB | Output is correct |
9 | Correct | 129 ms | 66248 KB | Output is correct |
10 | Correct | 302 ms | 65972 KB | Output is correct |
11 | Correct | 311 ms | 66084 KB | Output is correct |
12 | Correct | 357 ms | 66128 KB | Output is correct |
13 | Correct | 517 ms | 65960 KB | Output is correct |
14 | Correct | 1127 ms | 67276 KB | Output is correct |
15 | Correct | 298 ms | 65592 KB | Output is correct |
16 | Correct | 333 ms | 65772 KB | Output is correct |
17 | Correct | 255 ms | 66548 KB | Output is correct |
18 | Correct | 268 ms | 66484 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 637 ms | 362596 KB | Output is correct |
2 | Correct | 710 ms | 362560 KB | Output is correct |
3 | Correct | 3685 ms | 366868 KB | Output is correct |
4 | Correct | 635 ms | 362664 KB | Output is correct |
5 | Correct | 915 ms | 359816 KB | Output is correct |
6 | Correct | 833 ms | 359888 KB | Output is correct |
7 | Correct | 259 ms | 359896 KB | Output is correct |
8 | Correct | 707 ms | 359852 KB | Output is correct |
9 | Correct | 761 ms | 361084 KB | Output is correct |
10 | Correct | 849 ms | 359336 KB | Output is correct |
11 | Correct | 892 ms | 359688 KB | Output is correct |
12 | Correct | 1051 ms | 360108 KB | Output is correct |
13 | Correct | 2063 ms | 361252 KB | Output is correct |
14 | Execution timed out | 4035 ms | 363604 KB | Time limit exceeded |
15 | Halted | 0 ms | 0 KB | - |