| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 542232 | wildturtle | 팀들 (IOI15_teams) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "teams.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
int a[500005],b[500005],n,m;
int tree[40*500005],lef[40*500005],righ[40*500005];
int root[500005],k[500005],dp[500005];
int snode,prevroot;
set <int> st1;
set < pair <int,int> > st;
vector <int> v[500005];
inline void build(int node,int le,int ri) {
if(le==ri) {
tree[node]=0;
return;
}
snode++;
lef[node]=snode;
build(snode,le,(le+ri)/2);
snode++;
righ[node]=snode;
build(snode,(le+ri)/2+1,ri);
tree[node]=tree[lef[node]]+tree[righ[node]];
}
inline void update(int node,int prevnode,int le,int ri,int idx) {
if(ri<idx || le>idx) return;
if(le==ri) {
tree[node]=tree[prevnode]+1;
return;
}
if(idx<=(le+ri)/2) {
snode++; lef[node]=snode; righ[node]=righ[prevnode];
update(snode,lef[prevnode],le,(le+ri)/2,idx);
} else {
snode++; righ[node]=snode; lef[node]=lef[prevnode];
update(snode,righ[prevnode],(le+ri)/2+1,ri,idx);
}
tree[node]=tree[lef[node]]+tree[righ[node]];
}
inline int getans(int node,int start,int end,int le,int ri) {
if(ri<start || le>end) return 0;
if(start<=le && ri<=end) return tree[node];
return getans(lef[node],start,end,le,(le+ri)/2)+getans(righ[node],start,end,(le+ri)/2+1,ri);
}
inline int Z(int x,int y) {
return getans(root[y],y,n,1,n)-getans(root[x],y,n,1,n);
}
inline int go(int x,int y) {
int le=k[y]+1;
int ri=n;
int ans=0;
while(le<=ri) {
int mid=(le+ri)/2;
if(dp[x]-dp[y]< -(getans(root[k[y]],mid,n,1,n)-getans(root[k[x]],mid,n,1,n))) {
ans=mid; ri=mid-1;
} else le=mid+1;
}
return ans;
}
inline void add(int x) {
st1.insert(x);
if (!st1.size()) return;
int pat = -1, did = -1;
int tim;
if (*st1.begin() < x) pat = *(--st1.lower_bound(x));
if (st1.upper_bound(x) != st1.end()) did = *st1.upper_bound(x);
if (pat != -1 && did != -1) {
tim = go(pat, did);
if (tim) st.erase({tim,did});
}
if (pat != -1) {
tim = go(pat,x);
if (tim) st.insert({tim,x});
}
if (did != -1) {
tim = go(x, did);
if (tim) st.insert({tim,did});
}
}
inline void del(int x) {
if(!st1.count(x)) return;
st1.erase(x);
if(!st1.size()) return;
int pat=-1;
int did=-1;
if(*st1.begin()<x) pat=*(--st1.upper_bound(x));
if(st1.upper_bound(x)!=st1.end()) did=*st1.upper_bound(x);
int tim;
if(did!=-1) {
tim=go(x,did);
if(tim) st.erase({tim,did});
}
if(pat!=-1) {
tim=go(pat,x);
if(tim) st.erase({tim,x});
}
if(did!=-1 && pat!=-1) {
tim=go(pat,did);
if(tim) st.insert({tim,did});
}
}
inline int can(int M, int K[]) {
st.clear();
st1.clear();
m=M;
for(int i=1;i<=m;i++) {
k[i]=K[i-1];
dp[i]=0;
}
int sum=0;
for(int i=1;i<=m;i++) {
sum+=k[i];
}
if(sum>n) return 0;
sort(k+1,k+1+m);
dp[0]=0;
add(0);
for(int i=1;i<=m;i++) dp[i]=1e9;
for(int i=1;i<=m;i++) {
while(st.size()) {
multiset < pair <int,int> > :: iterator it = st.begin();
if((*it).f<=k[i]) del((*it).sc);
else break;
}
int idx=*(--st1.end());
dp[i]=dp[idx]+Z(k[idx],k[i])-k[i];
if(dp[i]<0) return 0;
add(i);
}
return 1;
}
inline void init(int N, int A[], int B[]) {
n=N;
for(int i=1;i<=n;i++) {
a[i]=A[i-1]; b[i]=B[i-1];
v[a[i]].pb(b[i]);
}
snode=1;
root[0]=snode;
build(1,1,n);
for(int i=1;i<=n;i++) {
prevroot=root[i-1];
root[i]=root[i-1];
for(int j=0;j<v[i].size();j++) {
snode++;
root[i]=snode;
update(root[i],prevroot,1,n,v[i][j]);
prevroot=root[i];
}
}
}