# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
396399 |
2021-04-29T23:32:49 Z |
peuch |
팀들 (IOI15_teams) |
C++17 |
|
1895 ms |
148060 KB |
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
int n;
pair<int, int> v[MAXN];
int bank[MAXN];
int m;
int k[MAXN];
vector<int> seg, e, d;
int create();
int copia(int pos);
int update(int pos, int ini, int fim, int id);
int query(int pos, int ini, int fim, int p, int q);
int bb(int pos1, int pos2, int ini, int fim, int val);
void init(int N, int A[], int B[]) {
n = N;
create();
bank[0] = create();
for(int i = 0; i < n; i++)
v[i + 1] = make_pair(A[i], B[i]);
sort(v + 1, v + 1 + n);
for(int i = 1; i <= n; i++)
bank[i] = update(bank[i - 1], 1, n, v[i].second);
}
int can(int M, int K[]) {
m = M;
for(int i = 0; i < m; i++)
k[i + 1] = K[i];
sort(k + 1, k + 1 + m);
stack<pair<int, pair<int, int> > > pilha;
pilha.push(make_pair(MAXN + 10, make_pair(0, 0)));
for(int i = 1; i <= m; i++){
int j = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN)) - v - 1;
if(j <= 0) return 0;
while(k[i] > pilha.top().first) pilha.pop();
int sum = query(bank[j], 1, n, k[i], k[i]) - query(bank[pilha.top().second.first], 1, n, k[i], k[i]);
int hmin = k[i] + 1;
int hmax = k[i];
while(!pilha.empty()){
if(sum >= k[i]) break;
int it = pilha.top().second.first;
hmax = pilha.top().first;
int diff = query(bank[j], 1, n, hmin, hmax) - query(bank[it], 1, n, hmin, hmax);
if(diff + sum >= k[i]){
int aux = query(bank[j], 1, n, 1, hmin - 1) - query(bank[it], 1, n, 1, hmin - 1);
hmax = bb(bank[j], bank[it], 1, n, k[i] - sum + aux);
diff = query(bank[j], 1, n, hmin, hmax) - query(bank[it], 1, n, hmin, hmax);
sum += diff;
break;
}
else sum += diff + pilha.top().second.second, hmin = hmax + 1, pilha.pop();
}
if(sum < k[i]) return 0;
pilha.push(make_pair(hmax, make_pair(j, sum - k[i])));
}
return 1;
}
int create(){
seg.push_back(0);
e.push_back(0);
d.push_back(0);
return seg.size() - 1;
}
int copia(int pos){
seg.push_back(seg[pos]);
e.push_back(e[pos]);
d.push_back(d[pos]);
return seg.size() - 1;
}
int update(int pos, int ini, int fim, int id){
if(ini > id || fim < id) return pos;
int newNode = copia(pos);
if(ini == fim){
seg[newNode]++;
return newNode;
}
int mid = (ini + fim) >> 1;
int aux = update(e[pos], ini, mid, id);
e[newNode] = aux;
aux = update(d[pos], mid + 1, fim, id);
d[newNode] = aux;
seg[newNode] = seg[e[newNode]] + seg[d[newNode]];
return newNode;
}
int query(int pos, int ini, int fim, int p, int q){
if(ini > q || fim < p) return 0;
if(ini >= p && fim <= q) return seg[pos];
int mid = (ini + fim) >> 1;
return query(e[pos], ini, mid, p, q) + query(d[pos], mid + 1, fim, p, q);
}
int bb(int pos1, int pos2, int ini, int fim, int val){
if(ini == fim) return ini;
int mid = (ini + fim) >> 1;
if(seg[e[pos1]] - seg[e[pos2]] >= val)
return bb(e[pos1], e[pos2], ini, mid, val);
return bb(d[pos1], d[pos2], mid + 1, fim, val - (seg[e[pos1]] - seg[e[pos2]]));
}
Compilation message
teams.cpp: In function 'int can(int, int*)':
teams.cpp:45:68: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
45 | int j = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN)) - v - 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int create()':
teams.cpp:81:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
81 | return seg.size() - 1;
| ~~~~~~~~~~~^~~
teams.cpp: In function 'int copia(int)':
teams.cpp:88:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
88 | return seg.size() - 1;
| ~~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
2 ms |
332 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
336 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
103 ms |
23080 KB |
Output is correct |
2 |
Correct |
113 ms |
23148 KB |
Output is correct |
3 |
Correct |
103 ms |
23168 KB |
Output is correct |
4 |
Correct |
109 ms |
23736 KB |
Output is correct |
5 |
Correct |
84 ms |
23136 KB |
Output is correct |
6 |
Correct |
75 ms |
23160 KB |
Output is correct |
7 |
Correct |
72 ms |
23148 KB |
Output is correct |
8 |
Correct |
76 ms |
23148 KB |
Output is correct |
9 |
Correct |
90 ms |
22528 KB |
Output is correct |
10 |
Correct |
83 ms |
22368 KB |
Output is correct |
11 |
Correct |
71 ms |
23556 KB |
Output is correct |
12 |
Correct |
71 ms |
22408 KB |
Output is correct |
13 |
Correct |
78 ms |
23476 KB |
Output is correct |
14 |
Correct |
74 ms |
22588 KB |
Output is correct |
15 |
Correct |
94 ms |
23068 KB |
Output is correct |
16 |
Correct |
96 ms |
23096 KB |
Output is correct |
17 |
Correct |
74 ms |
23496 KB |
Output is correct |
18 |
Correct |
81 ms |
23408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
23372 KB |
Output is correct |
2 |
Correct |
107 ms |
23392 KB |
Output is correct |
3 |
Correct |
453 ms |
26292 KB |
Output is correct |
4 |
Correct |
109 ms |
23824 KB |
Output is correct |
5 |
Correct |
137 ms |
23372 KB |
Output is correct |
6 |
Correct |
130 ms |
23440 KB |
Output is correct |
7 |
Correct |
82 ms |
23404 KB |
Output is correct |
8 |
Correct |
115 ms |
23460 KB |
Output is correct |
9 |
Correct |
85 ms |
22516 KB |
Output is correct |
10 |
Correct |
132 ms |
22684 KB |
Output is correct |
11 |
Correct |
141 ms |
23820 KB |
Output is correct |
12 |
Correct |
175 ms |
22660 KB |
Output is correct |
13 |
Correct |
359 ms |
23724 KB |
Output is correct |
14 |
Correct |
563 ms |
24832 KB |
Output is correct |
15 |
Correct |
236 ms |
23592 KB |
Output is correct |
16 |
Correct |
234 ms |
23520 KB |
Output is correct |
17 |
Correct |
153 ms |
23792 KB |
Output is correct |
18 |
Correct |
184 ms |
23796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
782 ms |
141328 KB |
Output is correct |
2 |
Correct |
757 ms |
141368 KB |
Output is correct |
3 |
Correct |
1716 ms |
141300 KB |
Output is correct |
4 |
Correct |
736 ms |
141288 KB |
Output is correct |
5 |
Correct |
600 ms |
141396 KB |
Output is correct |
6 |
Correct |
583 ms |
141300 KB |
Output is correct |
7 |
Correct |
468 ms |
141320 KB |
Output is correct |
8 |
Correct |
572 ms |
141356 KB |
Output is correct |
9 |
Correct |
517 ms |
141324 KB |
Output is correct |
10 |
Correct |
556 ms |
141380 KB |
Output is correct |
11 |
Correct |
621 ms |
141380 KB |
Output is correct |
12 |
Correct |
735 ms |
141316 KB |
Output is correct |
13 |
Correct |
1326 ms |
141384 KB |
Output is correct |
14 |
Correct |
1895 ms |
141392 KB |
Output is correct |
15 |
Correct |
932 ms |
148024 KB |
Output is correct |
16 |
Correct |
958 ms |
148060 KB |
Output is correct |
17 |
Correct |
679 ms |
147516 KB |
Output is correct |
18 |
Correct |
686 ms |
147328 KB |
Output is correct |