| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 831658 |
2023-08-20T12:00:19 Z |
qin |
Teams (IOI15_teams) |
C++14 |
|
4000 ms |
47332 KB |
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
struct st{
int a, b;
st(){}
st(int A, int B) : a(A), b(B) {}
bool operator <(const st &x) const{return b == x.b ? a < x.a : b < x.b;}
};
int base = 1;
struct seg{
vector<int> t;
void init(int n){
while(base < n) base <<= 1;
t.resize(base<<1);
} void update(int i, int w){
i += base-1; t[i] = w;
for(i>>=1; i; i>>=1) t[i] = t[i<<1] + t[i<<1|1];
} int Find(int i, int pocz, int kon){
if(pocz == kon) return pocz;
int ret = 0;
if(t[i<<1]) ret = Find(i<<1, pocz, (pocz+kon)>>1);
else ret = Find(i<<1|1, ((pocz+kon)>>1)+1, kon);
return ret;
} int findsmallest(){
if(!t[1]) return 0;
else return Find(1, 1, base);
}
};
vector<vector<st>> v;
int n;
int can(int m, int T[]){
vector<int> t(m);
for(int i = 0; i < m; ++i) t[i] = T[i];
int suma = 0;
for(int i = 0; i < m; ++i) suma += t[i];
if(suma > n) return 0;
seg seg;
seg.init(n);
int it = 0, tmp;
sort(t.begin(), t.end());
bool b = 1;
for(int i = 1; i <= n; ++i){
for(st u : v[i]) seg.update(u.a, u.b);
while(it != m && t[it] == i){
for(int j = 1; j <= i; ++j){
if(!seg.t[1]) { b = 0; break; }
tmp = seg.findsmallest();
seg.update(tmp, 0);
} ++it;
}
} return b;
}
void init(int N, int A[], int B[]){
n = N;
vector<int> a(n+1), b(n+1);
vector<st> t(n);
for(int i = 1; i <= n; ++i) a[i] = A[i-1];
for(int i = 1; i <= n; ++i) b[i] = B[i-1], t[i-1] = st(a[i], b[i]);
sort(t.begin(), t.end());
v.resize(n+2);
for(int i = 0; i < n; ++i) v[t[i].a].emplace_back(i+1, 1), v[t[i].b+1].emplace_back(i+1, 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
300 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
300 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
296 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
300 KB |
Output is correct |
| 22 |
Correct |
1 ms |
300 KB |
Output is correct |
| 23 |
Correct |
0 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
9492 KB |
Output is correct |
| 2 |
Correct |
31 ms |
9412 KB |
Output is correct |
| 3 |
Correct |
33 ms |
9420 KB |
Output is correct |
| 4 |
Correct |
34 ms |
9936 KB |
Output is correct |
| 5 |
Correct |
25 ms |
7980 KB |
Output is correct |
| 6 |
Correct |
21 ms |
7892 KB |
Output is correct |
| 7 |
Correct |
25 ms |
7924 KB |
Output is correct |
| 8 |
Correct |
25 ms |
7920 KB |
Output is correct |
| 9 |
Correct |
19 ms |
7560 KB |
Output is correct |
| 10 |
Correct |
22 ms |
7240 KB |
Output is correct |
| 11 |
Correct |
21 ms |
7368 KB |
Output is correct |
| 12 |
Correct |
22 ms |
7368 KB |
Output is correct |
| 13 |
Correct |
27 ms |
8100 KB |
Output is correct |
| 14 |
Correct |
25 ms |
9032 KB |
Output is correct |
| 15 |
Correct |
29 ms |
9288 KB |
Output is correct |
| 16 |
Correct |
30 ms |
9280 KB |
Output is correct |
| 17 |
Correct |
28 ms |
8092 KB |
Output is correct |
| 18 |
Correct |
25 ms |
7888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1723 ms |
9768 KB |
Output is correct |
| 2 |
Correct |
1983 ms |
9728 KB |
Output is correct |
| 3 |
Execution timed out |
4040 ms |
9680 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4043 ms |
47332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
