oj.uz

답안 #931747

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
931747 2024-02-22T10:24:04 Z winter0101 팀들 (IOI15_teams) C++17
77 / 100
 3156 ms 524288 KB 
#include<bits/stdc++.h>
#include "teams.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
struct node{
int l,r,val;
node(){
l=r=-1,val=0;
}
}st[20000009];
int nnode=0;
int build(int id,int l,int r){
if (l==r)return id;
int mid=(l+r)>>1;
st[id].l=build(id<<1,l,mid);
st[id].r=build(id<<1|1,mid+1,r);
return id;
}
int copy(int id){
st[++nnode]=st[id];
return nnode;
}
int update(int id,int l,int r,int u,int val){
if (l>u||r<u)return id;
if (l==r){
int newnode=copy(id);
st[newnode].val+=val;
return newnode;
}
int mid=(l+r)>>1;
int newnode=copy(id);
st[newnode].l=update(st[id].l,l,mid,u,val);
st[newnode].r=update(st[id].r,mid+1,r,u,val);
st[newnode].val=st[st[newnode].l].val+st[st[newnode].r].val;
return newnode;
}
int update_range(int id1,int id2,int l,int r,int u,int v){
if (l>v||r<u||u>v)return id1;
if (u<=l&&r<=v)return id2;
int mid=(l+r)>>1;
int newnode=copy(id1);
st[newnode].l=update_range(st[id1].l,st[id2].l,l,mid,u,v);
st[newnode].r=update_range(st[id1].r,st[id2].r,mid+1,r,u,v);
st[newnode].val=st[st[newnode].l].val+st[st[newnode].r].val;
return newnode;
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return st[id].val;
int mid=(l+r)>>1;
return get(st[id].l,l,mid,u,v)+get(st[id].r,mid+1,r,u,v);
}
const int maxn=5e5+9;
pii a[maxn];
int req[maxn];
int root[maxn];
vector<int>add[maxn],del[maxn];
int n;
void init(int N, int A[], int B[]) {
n=N;
for1(i,1,n){
a[i].fi=A[i-1],a[i].se=B[i-1];
}
sort(a+1,a+1+n,[](pii p,pii q){
if (p.se==q.se)return p.fi<q.fi;
return p.se<q.se;
});
for1(i,1,n){
add[a[i].fi].pb(i);
del[a[i].se+1].pb(i);
int l=1,r=n;
req[i]=0;
while (l<=r){
int mid=(l+r)/2;
if (a[mid].se>=i){
req[i]=mid;
r=mid-1;
}
else l=mid+1;
}
}
root[0]=build(1,1,n);
nnode=4*n;
for1(i,1,n){
int rt=root[i-1];
for(auto v:add[i]){
rt=update(rt,1,n,v,1);
}
for (auto v:del[i]){
rt=update(rt,1,n,v,-1);
}
root[i]=rt;
}
}
int cnt[maxn];
int can(int M, int K[]) {
long long sum=0;
for1(i,0,M-1)sum+=K[i];
if (sum>n)return 0;
int now=root[0],num=nnode;
for1(i,0,M-1)cnt[K[i]]++;
vector<int>gr;
for1(i,0,M-1)gr.pb(K[i]);
sort(all(gr));
gr.resize(distance(gr.begin(),unique(all(gr))));
bool fl=true;
for (auto v:gr){
int l=req[v],r=n,ans=-1;
while (l<=r){
int mid=(l+r)>>1;
if (get(root[v],1,n,req[v],mid)-get(now,1,n,req[v],mid)>=cnt[v]*v){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
if (ans==-1){
fl=false;
break;
}
now=update_range(now,root[v],1,n,req[v],ans);
}
nnode=num;
for1(i,0,M-1)cnt[K[i]]=0;
return fl;
}

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 258900 KB Output is correct
2 Correct 67 ms 258880 KB Output is correct
3 Correct 67 ms 258972 KB Output is correct
4 Correct 65 ms 258900 KB Output is correct
5 Correct 66 ms 258972 KB Output is correct
6 Correct 68 ms 258896 KB Output is correct
7 Correct 67 ms 258896 KB Output is correct
8 Correct 67 ms 258884 KB Output is correct
9 Correct 74 ms 258900 KB Output is correct
10 Correct 68 ms 258896 KB Output is correct
11 Correct 68 ms 258872 KB Output is correct
12 Correct 69 ms 258836 KB Output is correct
13 Correct 70 ms 258956 KB Output is correct
14 Correct 67 ms 258948 KB Output is correct
15 Correct 66 ms 258900 KB Output is correct
16 Correct 65 ms 258900 KB Output is correct
17 Correct 67 ms 258896 KB Output is correct
18 Correct 67 ms 258908 KB Output is correct
19 Correct 67 ms 259264 KB Output is correct
20 Correct 65 ms 258828 KB Output is correct
21 Correct 69 ms 258788 KB Output is correct
22 Correct 65 ms 258900 KB Output is correct
23 Correct 67 ms 259072 KB Output is correct
24 Correct 71 ms 258896 KB Output is correct
25 Correct 90 ms 259028 KB Output is correct
26 Correct 73 ms 258900 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 264912 KB Output is correct
2 Correct 177 ms 264772 KB Output is correct
3 Correct 174 ms 264772 KB Output is correct
4 Correct 177 ms 265936 KB Output is correct
5 Correct 122 ms 262516 KB Output is correct
6 Correct 123 ms 262472 KB Output is correct
7 Correct 115 ms 262388 KB Output is correct
8 Correct 119 ms 262384 KB Output is correct
9 Correct 107 ms 262688 KB Output is correct
10 Correct 155 ms 262220 KB Output is correct
11 Correct 116 ms 262340 KB Output is correct
12 Correct 114 ms 262260 KB Output is correct
13 Correct 129 ms 262584 KB Output is correct
14 Correct 117 ms 263324 KB Output is correct
15 Correct 146 ms 264680 KB Output is correct
16 Correct 153 ms 264520 KB Output is correct
17 Correct 122 ms 262516 KB Output is correct
18 Correct 118 ms 262296 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 265360 KB Output is correct
2 Correct 176 ms 265628 KB Output is correct
3 Correct 1042 ms 268528 KB Output is correct
4 Correct 165 ms 265932 KB Output is correct
5 Correct 664 ms 263156 KB Output is correct
6 Correct 587 ms 263164 KB Output is correct
7 Correct 119 ms 262736 KB Output is correct
8 Correct 471 ms 262740 KB Output is correct
9 Correct 93 ms 262732 KB Output is correct
10 Correct 115 ms 262596 KB Output is correct
11 Correct 137 ms 262584 KB Output is correct
12 Correct 688 ms 262700 KB Output is correct
13 Correct 922 ms 263228 KB Output is correct
14 Correct 1073 ms 266788 KB Output is correct
15 Correct 440 ms 265380 KB Output is correct
16 Correct 439 ms 265172 KB Output is correct
17 Correct 383 ms 262736 KB Output is correct
18 Correct 347 ms 262608 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3156 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -