# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
765336 |
2023-06-24T11:01:07 Z |
loctildore |
Teams (IOI15_teams) |
C++14 |
|
1773 ms |
133140 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
int m;
vector<pair<int,int>> vctr;
int carr[1069][1069];
struct node {
int l, r;
node *lft, *rht;
vector<int> endp;
node(int tl, int tr): l(tl), r(tr) {
if (l + 1 == r) {
lft = rht = NULL;
return;
}
lft = new node(l, (l + r) / 2);
rht = new node((l + r) / 2, r);
}
void upd(int tl, int tr) {
if (tr <= l || r <= tl) {
return;
}
if (tl <= l && r <= tr) {
endp.push_back(tr - 1);
return;
}
lft->upd(tl, tr);
rht->upd(tl, tr);
}
void srt() {
sort(all(endp));
if (l + 1 != r) {
lft->srt();
rht->srt();
}
}
int has(int x, int y) {
if (x < l || r <= x) {
return 0;
}
int rtn = end(endp) - lower_bound(all(endp), y);
if (l + 1 != r) {
rtn += lft->has(x, y);
rtn += rht->has(x, y);
}
return rtn;
}
void chckhas(int x) {
if (vctr[x].f < l || r <= vctr[x].f) return;
int tmp = 0;
if (endp.size()) for (int j = x; j < m; j++) {
if (endp[tmp] < vctr[j].f) {
tmp = lower_bound(begin(endp) + tmp, end(endp), vctr[j].f) - begin(endp);
}
carr[x][j] += endp.size() - tmp;
if (!carr[x][j]) break;
}
if (l + 1 != r) {
lft->chckhas(x);
rht->chckhas(x);
/*if (vctr[x].f < (l + r) / 2) {
lft->chckhas(x);
}
else rht->chckhas(x);*/
}
}
} *root;
int n;
void init(int N, int A[], int B[]) {
n = N;
root = new node(0, n + 69);
for (int i = 0; i < n; i++) {
root->upd(A[i], B[i] + 1);
}
root->srt();
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int can(int M, int K[]) {
int tot = 0;
vctr.clear();
while (pq.size()) pq.pop();
map<int, int> mp;
for (int i = 0; i < M; i++) {
tot += K[i];
mp[K[i]] += K[i];
}
for (auto t : mp) {
vctr.push_back(t);
}
m = vctr.size();
if (tot > n) return 0;
sort(all(vctr));
for (int i = 0; i < m; i++) {
for (int j = i; j < m; j++) {
carr[i][j] = 0;
//carr[i][j] = root->has(vctr[i].f, vctr[j].f);
//if (!carr[i][j]) break;
}
root->chckhas(i);
}
for (int i = 0; i < m; i++) {
for (int j = i; j < m; j++) {
int tmp = carr[i][j];
if (i > 0) tmp -= carr[i - 1][j];
if (j + 1 < m) tmp -= carr[i][j + 1];
if (i > 0 && j + 1 < m) tmp += carr[i - 1][j + 1];
if (tmp) {
pq.push({j, tmp});
}
//cout<<i<<j<<':'<<carr[i][j]<<' '<<endl;
}
//cout<<endl;
while (pq.size() && pq.top().f < i) pq.pop();
int tmp = vctr[i].s;
while (tmp && pq.size()) {
auto t = pq.top(); pq.pop();
int sub = min(tmp, t.s);
tmp -= sub;
t.s -= sub;
if (t.s) pq.push(t);
}
if (tmp) return 0;
}
return 1;
}
Compilation message
teams.cpp: In member function 'int node::has(int, int)':
teams.cpp:51:23: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
51 | int rtn = end(endp) - lower_bound(all(endp), y);
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'void node::chckhas(int)':
teams.cpp:64:64: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
64 | tmp = lower_bound(begin(endp) + tmp, end(endp), vctr[j].f) - begin(endp);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp:66:32: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
66 | carr[x][j] += endp.size() - tmp;
| ^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:104:15: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
104 | m = vctr.size();
| ~~~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 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 |
312 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
1 ms |
312 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
316 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
308 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
308 KB |
Output is correct |
26 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
27144 KB |
Output is correct |
2 |
Correct |
172 ms |
26740 KB |
Output is correct |
3 |
Correct |
158 ms |
25340 KB |
Output is correct |
4 |
Correct |
153 ms |
25920 KB |
Output is correct |
5 |
Correct |
23 ms |
16844 KB |
Output is correct |
6 |
Correct |
28 ms |
16308 KB |
Output is correct |
7 |
Correct |
23 ms |
16920 KB |
Output is correct |
8 |
Correct |
28 ms |
16852 KB |
Output is correct |
9 |
Correct |
53 ms |
25456 KB |
Output is correct |
10 |
Correct |
25 ms |
16160 KB |
Output is correct |
11 |
Correct |
26 ms |
18424 KB |
Output is correct |
12 |
Correct |
34 ms |
20192 KB |
Output is correct |
13 |
Correct |
57 ms |
22388 KB |
Output is correct |
14 |
Correct |
111 ms |
26276 KB |
Output is correct |
15 |
Correct |
122 ms |
24676 KB |
Output is correct |
16 |
Correct |
118 ms |
24648 KB |
Output is correct |
17 |
Correct |
26 ms |
16776 KB |
Output is correct |
18 |
Correct |
32 ms |
19108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
272 ms |
28052 KB |
Output is correct |
2 |
Correct |
238 ms |
27956 KB |
Output is correct |
3 |
Correct |
200 ms |
29476 KB |
Output is correct |
4 |
Correct |
137 ms |
25868 KB |
Output is correct |
5 |
Correct |
76 ms |
17632 KB |
Output is correct |
6 |
Correct |
72 ms |
17612 KB |
Output is correct |
7 |
Correct |
52 ms |
17636 KB |
Output is correct |
8 |
Correct |
67 ms |
17664 KB |
Output is correct |
9 |
Correct |
54 ms |
25408 KB |
Output is correct |
10 |
Correct |
24 ms |
16620 KB |
Output is correct |
11 |
Correct |
33 ms |
18680 KB |
Output is correct |
12 |
Correct |
203 ms |
20576 KB |
Output is correct |
13 |
Correct |
291 ms |
23104 KB |
Output is correct |
14 |
Correct |
263 ms |
27784 KB |
Output is correct |
15 |
Correct |
157 ms |
25632 KB |
Output is correct |
16 |
Correct |
144 ms |
25524 KB |
Output is correct |
17 |
Correct |
51 ms |
18428 KB |
Output is correct |
18 |
Correct |
60 ms |
21084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1773 ms |
129708 KB |
Output is correct |
2 |
Correct |
1622 ms |
129816 KB |
Output is correct |
3 |
Correct |
1382 ms |
133136 KB |
Output is correct |
4 |
Correct |
1208 ms |
125584 KB |
Output is correct |
5 |
Correct |
289 ms |
76920 KB |
Output is correct |
6 |
Correct |
263 ms |
77448 KB |
Output is correct |
7 |
Correct |
192 ms |
77504 KB |
Output is correct |
8 |
Correct |
253 ms |
76592 KB |
Output is correct |
9 |
Correct |
338 ms |
131936 KB |
Output is correct |
10 |
Correct |
142 ms |
83428 KB |
Output is correct |
11 |
Correct |
284 ms |
93024 KB |
Output is correct |
12 |
Correct |
807 ms |
105112 KB |
Output is correct |
13 |
Correct |
1134 ms |
107648 KB |
Output is correct |
14 |
Correct |
1562 ms |
133140 KB |
Output is correct |
15 |
Correct |
941 ms |
119448 KB |
Output is correct |
16 |
Correct |
911 ms |
118460 KB |
Output is correct |
17 |
Correct |
248 ms |
90800 KB |
Output is correct |
18 |
Correct |
256 ms |
91324 KB |
Output is correct |