# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
676039 |
2022-12-29T02:58:45 Z |
jamezzz |
Teams (IOI15_teams) |
C++17 |
|
1858 ms |
144320 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pf printf
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define ub(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
typedef pair<int,int> ii;
#define maxn 500005
struct node{
int s,e,m;vector<int> v;
node *l,*r;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void add(int x,int nv){
v.pb(nv);
if(s==e)return;
if(x<=m)l->add(x,nv);
else r->add(x,nv);
}
void init(){
sort(all(v));
if(s!=e)l->init(),r->init();
}
inline int get(int a,int b){
return ub(v,b)-lb(v,a);
}
int qry(int x,int y,int a,int b){
if(s==x&&e==y)return get(a,b);
if(y<=m)return l->qry(x,y,a,b);
if(x>m)return r->qry(x,y,a,b);
return l->qry(x,m,a,b)+r->qry(m+1,y,a,b);
}
int qryp(int a,int b,int n){
if(s==e)return s;
int g=r->get(a,b);
if(n-g>0){
return l->qryp(a,b,n-g);
}
return r->qryp(a,b,n);
}
}*rt=new node(1,maxn);
void init(int N,int A[],int B[]){
for(int i=0;i<N;++i)rt->add(B[i],A[i]);
rt->init();
}
map<int,int> good;
priority_queue<ii,vector<ii>,greater<ii>> rem;
void create(int i){
auto b=good.find(i);
auto a=prev(b);
int d=b->se-a->se;
int c=rt->qryp(a->fi+1,b->fi,d)+1;
rem.push({c,b->fi});
}
void process(int K){
while(!rem.empty()&&rem.top().fi<=K){
auto[_,i]=rem.top();
rem.pop();
auto it=good.find(i);
if(it==good.end())continue;
auto nit=next(it);
int nx=-1;
if(nit!=good.end())nx=nit->fi;
good.erase(it);
if(nx!=-1)create(nx);
}
}
void insert(int K,int v){
good[K]=v;
if(sz(good)==1)return;
create(K);
}
int can(int M,int K[]){
good.clear();
while(!rem.empty())rem.pop();
sort(K,K+M);
int acc=0;
for(int i=0;i<M;++i){
acc+=K[i];
if(i!=M-1&&K[i]==K[i+1])continue;
process(K[i]);
int dp=rt->qry(K[i],maxn,1,K[i]);
if(!good.empty()){
auto it=--good.end();
dp=min(dp,it->se+rt->qry(K[i],maxn,it->fi+1,K[i]));
}
dp-=acc;
//pf("K: %d, dp: %d\n",K[i],dp);
if(dp<0)return 0;
insert(K[i],dp);
acc=0;
}
return 1;
}
Compilation message
teams.cpp: In member function 'int node::get(int, int)':
teams.cpp:35:17: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
35 | return ub(v,b)-lb(v,a);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
62832 KB |
Output is correct |
2 |
Correct |
50 ms |
62796 KB |
Output is correct |
3 |
Correct |
51 ms |
62812 KB |
Output is correct |
4 |
Correct |
51 ms |
62892 KB |
Output is correct |
5 |
Correct |
55 ms |
63048 KB |
Output is correct |
6 |
Correct |
53 ms |
62988 KB |
Output is correct |
7 |
Correct |
52 ms |
62924 KB |
Output is correct |
8 |
Correct |
62 ms |
62888 KB |
Output is correct |
9 |
Correct |
52 ms |
62924 KB |
Output is correct |
10 |
Correct |
51 ms |
62924 KB |
Output is correct |
11 |
Correct |
52 ms |
62848 KB |
Output is correct |
12 |
Correct |
53 ms |
62832 KB |
Output is correct |
13 |
Correct |
52 ms |
62924 KB |
Output is correct |
14 |
Correct |
55 ms |
62932 KB |
Output is correct |
15 |
Correct |
59 ms |
62856 KB |
Output is correct |
16 |
Correct |
51 ms |
62844 KB |
Output is correct |
17 |
Correct |
51 ms |
62904 KB |
Output is correct |
18 |
Correct |
51 ms |
62788 KB |
Output is correct |
19 |
Correct |
60 ms |
62904 KB |
Output is correct |
20 |
Correct |
51 ms |
62872 KB |
Output is correct |
21 |
Correct |
51 ms |
62836 KB |
Output is correct |
22 |
Correct |
50 ms |
62904 KB |
Output is correct |
23 |
Correct |
50 ms |
62852 KB |
Output is correct |
24 |
Correct |
51 ms |
62844 KB |
Output is correct |
25 |
Correct |
50 ms |
62904 KB |
Output is correct |
26 |
Correct |
50 ms |
62824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
77232 KB |
Output is correct |
2 |
Correct |
213 ms |
77376 KB |
Output is correct |
3 |
Correct |
240 ms |
77356 KB |
Output is correct |
4 |
Correct |
220 ms |
77996 KB |
Output is correct |
5 |
Correct |
148 ms |
73572 KB |
Output is correct |
6 |
Correct |
158 ms |
73600 KB |
Output is correct |
7 |
Correct |
153 ms |
73628 KB |
Output is correct |
8 |
Correct |
185 ms |
73600 KB |
Output is correct |
9 |
Correct |
107 ms |
73148 KB |
Output is correct |
10 |
Correct |
102 ms |
72192 KB |
Output is correct |
11 |
Correct |
98 ms |
72252 KB |
Output is correct |
12 |
Correct |
114 ms |
73324 KB |
Output is correct |
13 |
Correct |
163 ms |
73564 KB |
Output is correct |
14 |
Correct |
145 ms |
75280 KB |
Output is correct |
15 |
Correct |
195 ms |
77296 KB |
Output is correct |
16 |
Correct |
230 ms |
77168 KB |
Output is correct |
17 |
Correct |
109 ms |
74012 KB |
Output is correct |
18 |
Correct |
110 ms |
73908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
78024 KB |
Output is correct |
2 |
Correct |
223 ms |
78188 KB |
Output is correct |
3 |
Correct |
378 ms |
81392 KB |
Output is correct |
4 |
Correct |
221 ms |
77948 KB |
Output is correct |
5 |
Correct |
201 ms |
74268 KB |
Output is correct |
6 |
Correct |
199 ms |
74180 KB |
Output is correct |
7 |
Correct |
145 ms |
74240 KB |
Output is correct |
8 |
Correct |
202 ms |
74220 KB |
Output is correct |
9 |
Correct |
96 ms |
73072 KB |
Output is correct |
10 |
Correct |
107 ms |
72576 KB |
Output is correct |
11 |
Correct |
104 ms |
72928 KB |
Output is correct |
12 |
Correct |
191 ms |
73048 KB |
Output is correct |
13 |
Correct |
361 ms |
73972 KB |
Output is correct |
14 |
Correct |
398 ms |
79720 KB |
Output is correct |
15 |
Correct |
269 ms |
77988 KB |
Output is correct |
16 |
Correct |
275 ms |
78000 KB |
Output is correct |
17 |
Correct |
183 ms |
74688 KB |
Output is correct |
18 |
Correct |
169 ms |
74328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1136 ms |
137552 KB |
Output is correct |
2 |
Correct |
1069 ms |
137532 KB |
Output is correct |
3 |
Correct |
1496 ms |
144320 KB |
Output is correct |
4 |
Correct |
1108 ms |
137056 KB |
Output is correct |
5 |
Correct |
728 ms |
115920 KB |
Output is correct |
6 |
Correct |
686 ms |
115896 KB |
Output is correct |
7 |
Correct |
544 ms |
116052 KB |
Output is correct |
8 |
Correct |
639 ms |
115640 KB |
Output is correct |
9 |
Correct |
301 ms |
111452 KB |
Output is correct |
10 |
Correct |
282 ms |
109768 KB |
Output is correct |
11 |
Correct |
322 ms |
110560 KB |
Output is correct |
12 |
Correct |
531 ms |
111396 KB |
Output is correct |
13 |
Correct |
1383 ms |
115888 KB |
Output is correct |
14 |
Correct |
1858 ms |
139464 KB |
Output is correct |
15 |
Correct |
1085 ms |
134196 KB |
Output is correct |
16 |
Correct |
1118 ms |
135264 KB |
Output is correct |
17 |
Correct |
608 ms |
124220 KB |
Output is correct |
18 |
Correct |
586 ms |
122916 KB |
Output is correct |