| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 863791 | sunwukong123 | 팀들 (IOI15_teams) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 500005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
struct node2 {
int s,e,val;
node2 *l, *r;
node2(int _s, int _e){
s=_s;e=_e;
val=0;
l=r=nullptr;
}
node2* update(int x, int nval){ // point add, range query
int m=(s+e)/2;
node2* curnode=new node2(s,e);curnode->val=val;
if(l==nullptr){
l=new node2(s,m);
}
if(r==nullptr){
r=new node2(m+1,e);
}
if(s==e){
curnode->val+=nval;
return curnode;
}
if(x>m){
node2* newr=r->update(x,nval);
curnode->r=newr;
curnode->l=l;
curnode->val=curnode->r->val+curnode->l->val;
return curnode;
} else{
node2* newl=l->update(x,nval);
curnode->l=newl;
curnode->r=r;
curnode->val=curnode->r->val+curnode->l->val;
return curnode;
}
}
int query(int x, int y){
int m=(s+e)/2;
if(x>y)return 0;
if(s==x&&e==y)return val;
if(x>m)return r?r->query(x,y):0;
else if(y<=m)return l?l->query(x,y):0;
else return (l?l->query(x,m):0) + (r?r->query(m+1,y):0);
}
} *segx[MAXN],*segy[MAXN];
int n;
int mpx[MAXN],mpy[MAXN];
void init(int N, int A[], int B[]) {
map<int,int>mpx,mpy;
n=N;
vector<pi> va, vb;
for(int i=0;i<n;i++){
va.push_back({A[i],i});
vb.push_back({B[i],i});
}
sort(va.begin(),va.end());
sort(vb.begin(),vb.end());
for(int i=0;i<(int)va.size();i++){
A[va[i].second]=i+1;
mpx[va[i].first]=i+1;
}
for(int i=1;i<=n;i++){
auto it=mpx.lower_bound(i);
if(it->first != i && it != mpx.begin()){
mpx[i]=prev(it)->second;
}
debug(i,mpx[i]);
}
for(int i=(int)vb.size()-1;i>=0;i--){
B[vb[i].second]=i+1;
mpy[vb[i].first]=i+1;
}
for(int i=1;i<=n;i++){
auto it=mpy.lower_bound(i);
if(it==mpy.end()){
mpy[i]=n;
continue;
}
if(it->first != i){
mpy[i]=it->second;
}
debug(i,mpy[i]);
}
for(int i=1;i<=n;i++){
::mpx[i]=mpx[i];
::mpy[i]=mpy[i];
}
vector<int> Vx[n+5];
vector<int> Vy[n+5];
for(int i=0;i<n;i++){
debug(A[i],B[i]);
Vx[A[i]].push_back(B[i]);
Vy[B[i]].push_back(A[i]);
}
/*
for(int i=1;i<=n;i++){
sort(Vx[i].begin(),Vx[i].end());
sort(Vy[i].begin(),Vy[i].end());
}*/
segy[0]=new node2(0,n);
segx[0]=new node2(0,n);
for(int i=1;i<=n;i++){
segx[i]=segx[i-1];
for(auto x:Vx[i]){
segx[i]=segx[i]->update(x,1);
}
}
for(int i=1;i<=n;i++){
segy[i]=segy[i-1];
for(auto x:Vy[i]){
segy[i]=segy[i]->update(x,1);
}
}
}
int Lkth(node2* s2, node2* s1, int k){
if(s2->s == s2->e){
return s2->s;
}
int R2=s2->r?s2->r->val:0;
int L2=s2->l?s2->l->val:0;
int R1=0;
int L1=0;
if(s1){
R1=s1->r?s1->r->val:0;
L1=s1->l?s1->l->val:0;
}
int rval=R2-R1;
int lval=L2-L1;
if(lval>=k){
int s2m=(s2->s+s2->e)/2;
if(s2->l==nullptr)return s;
if(s1->l==nullptr){
return Lkth(s2->l,nullptr,k);
} else{
return Lkth(s2->l, s1->l, k);
}
//if(s1->l==nullptr)s1->l=new node2(s1->s,s1m);
}
else {
int s2m=(s2->s+s2->e)/2;
if(s2->r==nullptr)return s2m+1;
if(s1->r==nullptr){
return Lkth(s2->r,nullptr,k-lval);
} else{
return Lkth(s2->r,s1->r,k-lval);
}
//if(s1->r==nullptr)s1->r=new node2(s1m+1,s1->e);
}
}
int can(int m, int K[]) {
map<int,int> mp;
int tot=0;
for(int i=0;i<m;i++){
mp[K[i]]++;
tot+=K[i];
}
if(tot>n)return 0;
stack<pi> stk;
stk.push({0,n});
for(auto l:mp){
int x=mpx[l.first],y=mpy[l.first],freq=l.second*l.first;
bool done=0;
while(stk.size()){
//debug(freq);
pi cur=stk.top();
int lf=cur.first;
int top=cur.second;
if(top<y){
stk.pop();
continue;
}
int S=segx[x]->query(y,top) - segx[lf]->query(y,top);
if(S<freq){
freq-=S;
y=top+1;
stk.pop();
} else{
done=1;
int b=segx[x]->query(0,y-1) - segx[lf]->query(0,y-1);
int newy=Lkth(segx[x], segx[lf], b+freq);
//find the smallest Y that is OK
int need=freq-(segx[x]->query(y,newy-1) - segx[lf]->query(y,newy-1));
int e=segy[newy]->query(0,lf)-segy[newy-1]->query(0,lf);
int newx=Lkth(segy[newy],segy[newy-1],e+need);
stk.push({newx,newy});
if(newx != mpx[l.first] && newy != mpy[l.first])stk.push({mpx[l.first],newy-1});
//debug(newx,newy);
break;
}
}
if(done==0)return 0;
}
return 1;
}