# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
384907 |
2021-04-02T15:48:45 Z |
LucaDantas |
Teams (IOI15_teams) |
C++17 |
|
3635 ms |
269276 KB |
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
#define all(a) (a).begin(), (a).end()
constexpr int maxn = 2e5+10;
int n, ind[maxn];
struct Node
{
Node *l, *r;
int v;
Node() : l(this), r(this), v(0) {}
} *root[maxn];
struct PersistentSegmentTree
{
Node* upd(Node* base, int i, int j, int pos, int v) {
Node *node = new Node();
*node = *base;
node->v += v;
if(i == j) return node;
int m = (i+j) >> 1;
if(pos <= m) node->l = upd(node->l, i, m, pos, v);
else node->r = upd(node->r, m+1, j, pos, v);
return node;
}
int query(Node* prev, Node* now, int i, int j, int l, int r) {
if(i > r || j < l) return 0;
if(i >= l && j <= r) return now->v - prev->v;
int m = (i+j) >> 1;
return query(prev->l, now->l, i, m, l, r) + query(prev->r, now->r, m+1, j, l, r);
}
int get(int l, int r, int k) {
return query(root[ind[l]], root[ind[r]], 1, n, k, n);
}
} seg;
pair<int,int> ranges[maxn];
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < N; i++)
ranges[i] = {A[i], B[i]};
sort(ranges, ranges+N);
root[0] = new Node();
for(int i = 1, ptr = 0; i <= N; i++) {
for(; ptr < N && ranges[ptr].first == i; ptr++)
root[ptr+1] = seg.upd(root[ptr], 1, n, ranges[ptr].second, 1);
ind[i] = ptr;
}
}
int fq[maxn];
long long dp[maxn]; // qual o menor valor de |v(S)| - |S| pra um subset até i
int can(int M, int K[]) {
vector<int> V(M);
for(int i = 0; i < M; i++)
V[i] = K[i], ++fq[K[i]];
sort(all(V));
V.erase(unique(all(V)), V.end());
M = (int)V.size();
bool ok = 1;
for(int i = 0; i < M; i++) {
int k = V[i];
dp[i] = seg.get(0, k, k) - 1ll * fq[k] * k;
for(int j = 0; j < i; j++)
dp[i] = min(dp[i], dp[j] + seg.get(V[j], k, k) - 1ll * fq[k] * k);
ok &= dp[i] >= 0;
}
for(int i = 0; i < M; i++)
dp[i] = fq[V[i]] = 0;
return ok;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
492 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
2 ms |
364 KB |
Output is correct |
9 |
Correct |
2 ms |
364 KB |
Output is correct |
10 |
Correct |
2 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
2 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
152 ms |
58988 KB |
Output is correct |
2 |
Correct |
162 ms |
59116 KB |
Output is correct |
3 |
Correct |
130 ms |
58988 KB |
Output is correct |
4 |
Correct |
132 ms |
59884 KB |
Output is correct |
5 |
Correct |
115 ms |
58988 KB |
Output is correct |
6 |
Correct |
109 ms |
59032 KB |
Output is correct |
7 |
Correct |
114 ms |
58988 KB |
Output is correct |
8 |
Correct |
116 ms |
58988 KB |
Output is correct |
9 |
Correct |
88 ms |
57068 KB |
Output is correct |
10 |
Correct |
90 ms |
56940 KB |
Output is correct |
11 |
Correct |
94 ms |
60012 KB |
Output is correct |
12 |
Correct |
97 ms |
56812 KB |
Output is correct |
13 |
Correct |
105 ms |
59884 KB |
Output is correct |
14 |
Correct |
101 ms |
57580 KB |
Output is correct |
15 |
Correct |
124 ms |
59008 KB |
Output is correct |
16 |
Correct |
124 ms |
59116 KB |
Output is correct |
17 |
Correct |
99 ms |
59884 KB |
Output is correct |
18 |
Correct |
102 ms |
59884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3355 ms |
59716 KB |
Output is correct |
2 |
Correct |
2953 ms |
59584 KB |
Output is correct |
3 |
Correct |
240 ms |
63084 KB |
Output is correct |
4 |
Correct |
131 ms |
60524 KB |
Output is correct |
5 |
Correct |
3530 ms |
60396 KB |
Output is correct |
6 |
Correct |
3050 ms |
60312 KB |
Output is correct |
7 |
Correct |
3635 ms |
60416 KB |
Output is correct |
8 |
Correct |
3097 ms |
60140 KB |
Output is correct |
9 |
Correct |
89 ms |
57360 KB |
Output is correct |
10 |
Correct |
93 ms |
57452 KB |
Output is correct |
11 |
Correct |
148 ms |
60780 KB |
Output is correct |
12 |
Correct |
1338 ms |
58004 KB |
Output is correct |
13 |
Correct |
390 ms |
61292 KB |
Output is correct |
14 |
Correct |
266 ms |
62316 KB |
Output is correct |
15 |
Correct |
219 ms |
60396 KB |
Output is correct |
16 |
Correct |
219 ms |
60524 KB |
Output is correct |
17 |
Correct |
250 ms |
61420 KB |
Output is correct |
18 |
Correct |
219 ms |
61376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
533 ms |
269276 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |