# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
56230 |
2018-07-10T11:04:56 Z |
aome |
Teams (IOI15_teams) |
C++17 |
|
2653 ms |
240388 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5000005;
const int M = 2005;
int n;
int ver[N];
int sum[M][M];
int g[M], h[M], f[M][M];
vector< pair<int, int> > seg;
struct SegmentTree {
struct Node {
int cnt, l, r;
};
int num;
Node T[20 * N];
#define mid ((l + r) >> 1)
void build(int i, int l, int r) {
if (l == r) return;
T[i].l = ++num;
build(T[i].l, l, mid);
T[i].r = ++num;
build(T[i].r, mid + 1, r);
}
void upd(int i, int j, int l, int r, int p) {
T[j].cnt = T[i].cnt + 1;
if (l == r) return;
if (mid >= p) {
T[j].l = ++num, T[j].r = T[i].r;
upd(T[i].l, T[j].l, l, mid, p);
}
else {
T[j].l = T[i].l, T[j].r = ++num;
upd(T[i].r, T[j].r, mid + 1, r, p);
}
}
int get(int i, int l, int r, int L, int R) {
if (l > R || L > r) return 0;
if (L <= l && r <= R) return T[i].cnt;
return get(T[i].l, l, mid, L, R) + get(T[i].r, mid + 1, r, L, R);
}
#undef mid
} IT;
void init(int _n, int A[], int B[]) {
n = _n;
for (int i = 0; i < n; ++i) {
seg.push_back({A[i], B[i]});
}
sort(seg.begin(), seg.end());
IT.build(0, 1, n);
for (int i = 0; i < n; ++i) {
ver[i + 1] = ++IT.num;
if (seg[i].first < M) g[seg[i].first] = i;
IT.upd(ver[i], ver[i + 1], 1, n, seg[i].second);
}
for (int i = 0; i < n; ++i) {
int x = seg[i].first;
int y = seg[i].second;
if (y < M) h[y]++;
if (x < M && g[x] == i) {
for (int j = x; j < M; ++j) {
sum[x][j] = sum[x][j - 1] + h[j];
}
}
}
}
int can(int m, int K[]) {
// cout << "#query\n";
sort(K, K + m);
vector< pair<int, int> > vec;
for (int i = 0; i < m; ++i) {
int j = i;
while (j < m && K[j] == K[i]) j++;
vec.push_back({K[i], j - i}), i = j - 1;
}
int sz = vec.size();
for (int i = 0; i < sz; ++i) {
h[i] = 0;
g[i] = lower_bound(seg.begin(), seg.end(), make_pair(vec[i].first + 1, 0)) - seg.begin();
}
for (int i = 0; i < sz; ++i) {
for (int j = i; j < (sz - 1); ++j) {
int l = vec[j].first, r = vec[j + 1].first - 1;
if (r < M) {
int x = 0;
if (g[i]) x = seg[g[i] - 1].first;
f[i][j] = sum[x][r] - sum[x][l - 1];
}
else {
f[i][j] = IT.get(ver[g[i]], 1, n, l, r);
}
}
f[i][sz - 1] = IT.get(ver[g[i]], 1, n, vec[sz - 1].first, n);
// cout << g[i] << '\n';
// for (int j = i; j < sz; ++j) cout << f[i][j] << ' ';
// cout << '\n';
}
bool fail = 0;
for (int i = 0; i < sz; ++i) {
int need = vec[i].second * vec[i].first;
for (int j = i; j < sz; ++j) {
f[i][j] -= h[j];
int tmp = min(need, f[i][j]);
h[j] += tmp, need -= tmp;
}
if (need) fail = 1;
}
return !fail;
}
Compilation message
teams.cpp: In function 'int can(int, int*)':
teams.cpp:89:19: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int sz = vec.size();
~~~~~~~~^~
teams.cpp:92:78: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
g[i] = lower_bound(seg.begin(), seg.end(), make_pair(vec[i].first + 1, 0)) - seg.begin();
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
484 KB |
Output is correct |
3 |
Correct |
3 ms |
944 KB |
Output is correct |
4 |
Correct |
4 ms |
1108 KB |
Output is correct |
5 |
Correct |
3 ms |
1108 KB |
Output is correct |
6 |
Correct |
3 ms |
1108 KB |
Output is correct |
7 |
Correct |
2 ms |
1108 KB |
Output is correct |
8 |
Correct |
3 ms |
1108 KB |
Output is correct |
9 |
Correct |
3 ms |
1108 KB |
Output is correct |
10 |
Correct |
2 ms |
1108 KB |
Output is correct |
11 |
Correct |
3 ms |
1108 KB |
Output is correct |
12 |
Correct |
2 ms |
1108 KB |
Output is correct |
13 |
Correct |
2 ms |
1108 KB |
Output is correct |
14 |
Correct |
2 ms |
1108 KB |
Output is correct |
15 |
Correct |
2 ms |
1108 KB |
Output is correct |
16 |
Correct |
3 ms |
1132 KB |
Output is correct |
17 |
Correct |
3 ms |
1132 KB |
Output is correct |
18 |
Correct |
0 ms |
1132 KB |
Output is correct |
19 |
Correct |
2 ms |
1132 KB |
Output is correct |
20 |
Correct |
2 ms |
1132 KB |
Output is correct |
21 |
Correct |
4 ms |
1132 KB |
Output is correct |
22 |
Correct |
2 ms |
1132 KB |
Output is correct |
23 |
Correct |
2 ms |
1132 KB |
Output is correct |
24 |
Correct |
2 ms |
1132 KB |
Output is correct |
25 |
Correct |
2 ms |
1132 KB |
Output is correct |
26 |
Correct |
3 ms |
1132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
40304 KB |
Output is correct |
2 |
Correct |
89 ms |
40304 KB |
Output is correct |
3 |
Correct |
102 ms |
40304 KB |
Output is correct |
4 |
Correct |
108 ms |
40304 KB |
Output is correct |
5 |
Correct |
58 ms |
40304 KB |
Output is correct |
6 |
Correct |
47 ms |
40304 KB |
Output is correct |
7 |
Correct |
45 ms |
40304 KB |
Output is correct |
8 |
Correct |
48 ms |
40304 KB |
Output is correct |
9 |
Correct |
32 ms |
40304 KB |
Output is correct |
10 |
Correct |
32 ms |
40304 KB |
Output is correct |
11 |
Correct |
39 ms |
40304 KB |
Output is correct |
12 |
Correct |
50 ms |
40304 KB |
Output is correct |
13 |
Correct |
60 ms |
40304 KB |
Output is correct |
14 |
Correct |
60 ms |
40304 KB |
Output is correct |
15 |
Correct |
81 ms |
40304 KB |
Output is correct |
16 |
Correct |
61 ms |
40304 KB |
Output is correct |
17 |
Correct |
42 ms |
40304 KB |
Output is correct |
18 |
Correct |
38 ms |
40304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
40428 KB |
Output is correct |
2 |
Correct |
208 ms |
40432 KB |
Output is correct |
3 |
Correct |
200 ms |
41188 KB |
Output is correct |
4 |
Correct |
75 ms |
41188 KB |
Output is correct |
5 |
Correct |
202 ms |
41188 KB |
Output is correct |
6 |
Correct |
177 ms |
41188 KB |
Output is correct |
7 |
Correct |
194 ms |
41188 KB |
Output is correct |
8 |
Correct |
176 ms |
41188 KB |
Output is correct |
9 |
Correct |
30 ms |
41188 KB |
Output is correct |
10 |
Correct |
34 ms |
41188 KB |
Output is correct |
11 |
Correct |
45 ms |
41188 KB |
Output is correct |
12 |
Correct |
127 ms |
41188 KB |
Output is correct |
13 |
Correct |
372 ms |
41188 KB |
Output is correct |
14 |
Correct |
298 ms |
41188 KB |
Output is correct |
15 |
Correct |
104 ms |
41188 KB |
Output is correct |
16 |
Correct |
139 ms |
41188 KB |
Output is correct |
17 |
Correct |
141 ms |
41188 KB |
Output is correct |
18 |
Correct |
123 ms |
41188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1275 ms |
158552 KB |
Output is correct |
2 |
Correct |
1206 ms |
165876 KB |
Output is correct |
3 |
Correct |
1056 ms |
174352 KB |
Output is correct |
4 |
Correct |
476 ms |
175420 KB |
Output is correct |
5 |
Correct |
920 ms |
181984 KB |
Output is correct |
6 |
Correct |
933 ms |
186700 KB |
Output is correct |
7 |
Correct |
967 ms |
191300 KB |
Output is correct |
8 |
Correct |
877 ms |
195976 KB |
Output is correct |
9 |
Correct |
164 ms |
195976 KB |
Output is correct |
10 |
Correct |
186 ms |
195976 KB |
Output is correct |
11 |
Correct |
292 ms |
200240 KB |
Output is correct |
12 |
Correct |
2653 ms |
213244 KB |
Output is correct |
13 |
Correct |
1311 ms |
218768 KB |
Output is correct |
14 |
Correct |
940 ms |
226912 KB |
Output is correct |
15 |
Correct |
582 ms |
226912 KB |
Output is correct |
16 |
Correct |
646 ms |
227056 KB |
Output is correct |
17 |
Correct |
500 ms |
233780 KB |
Output is correct |
18 |
Correct |
490 ms |
240388 KB |
Output is correct |