제출 #537913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537913		new_acc	팀들 (IOI15_teams)	C++14	0 / 100	2193 ms	369692 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e5+10;
const int SS=1<<19;
struct item{
	item *l,*r;
	int val;
};
pitem wsk[N];
pair<int,int>t[N];
bitset<N>ok;
int n,dp[N],w[N];
void upd(int ind,pitem v,pitem nv,int p=0,int k=SS-1){
	nv->val=v->val+1;
	if(!(v->r)){
		nv->r=nullptr,nv->l=nullptr;
		return;
	}
	if(ind<=(p+k)>>1){
		nv->r=v->r,nv->l=new item;
		upd(ind,v->l,nv->l,p,(p+k)>>1);
	}else{
		nv->l=v->l,nv->r=new item;
		upd(ind,v->r,nv->r,((p+k)>>1)+1,k);
	}
}
void build(pitem v,int akt){
	if(!v) return;
	v->val=0;
	if(akt>SS) v->l=nullptr,v->r=nullptr;
	else{
		v->r=new item,v->l=new item;
		build(v->r,(akt<<1)+1),build(v->l,(akt<<1));
	}
}
int Query(pitem v,int a,int b,int p=0,int k=SS-1){
	if(p>b or k<a) return 0;
	if(p>=a and k<=b) return v->val;
	else return Query(v->l,a,b,p,(p+k)>>1)+Query(v->r,a,b,((p+k)>>1)+1,k);
}
int bs(int x){
	int pocz=1,kon=n,res,sr;
	while(pocz<=kon){
		sr=(pocz+kon)>>1;
		if(t[sr].fi<=x) res=sr,pocz=sr+1;
		else kon=sr-1;
	}
	return res;
}
int sq(int a,int b){
	return Query(wsk[bs(a)],b,SS-1);
}
int bs2(int i,int j,int pocz,int kon){
	int sr,res=kon+1;
	while(pocz<=kon){
		sr=(pocz+kon)>>1;
		int val1=sq(w[sr],w[sr])-sq(w[i],w[sr])+dp[i]-w[sr];
		int val2=sq(w[sr],w[sr])-sq(w[j],w[sr])+dp[j]-w[sr];
		if(val1<=val2) kon=sr-1,res=sr;
		else pocz=sr+1;
	}
	return res;
}
void init(int nn,int a[],int b[]){
	n=nn;
	for(int i=0;i<n;i++) t[i+1]={a[i],b[i]};
	sort(t+1,t+1+n);
	wsk[0]=new item;
	build(wsk[0],1);
	for(int i=1;i<=n;i++){
		wsk[i]=new item;
		upd(t[i].se,wsk[i-1],wsk[i]);
	}
}
int can(int m,int vv[]){
	sort(vv,vv+m);
	for(int i=0;i<m;i++) w[i+1]=vv[i];
	dp[1]=sq(w[1],w[1])-w[1];
	if(m==1) return dp[1]>=0;
	for(int i=1;i<=m;i++) ok[i]=0;
	set<int> curr;
	set<pair<int,bool> >act;
	ok[1]=1;
	curr.insert(1),act.insert({2,0});
	while(1){
		auto it2=act.begin();
		pair<int,bool> v=*it2;
		act.erase(it2);
		if(v.fi>m) break;
		if(v.se){	
			if(!ok[v.fi]) continue;
			ok[v.fi]=0;
			auto it=curr.lower_bound(v.fi);
			it--;			
			int mn=*it;
			it++,it++;
			if(it!=curr.end()){
				int wi=*it;
				curr.erase(it);
				act.insert({bs2(mn,wi,v.fi+1,m),1});
			}
		}else{
			auto it=curr.end();
			it--;
			dp[v.fi]=sq(w[v.fi],w[v.fi])-sq(w[*it],w[v.fi])+dp[*it]-w[v.fi];
			curr.insert(v.fi);
			it=curr.end();
			it--,it--;
			act.insert({bs2(*it,v.fi,v.fi+1,m),1});
			act.insert({v.fi+1,0});
			ok[v.fi]=1;
		}
	}
	for(int i=1;i<=m;i++) if(dp[i]<0) return 0;
	return 1;
}
/*int main(){
	vi a,b;
	int n;
	cin>>n;
	for(int i=1,x,d;i<=n;i++){
		cin>>x>>d;
		a.push_back(x),b.push_back(d);
	}
	init(n,a,b);
	int m;
	cin>>m;
	vi pom;
	for(int i=1,x;i<=m;i++){
		cin>>x;
		pom.push_back(x);
	}
	cout<<can(m,pom)<<"\n";
}*/

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'int bs(int)':
teams.cpp:55:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |  return res;
      |         ^~~
teams.cpp: In function 'int sq(int, int)':
teams.cpp:58:14: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  return Query(wsk[bs(a)],b,SS-1);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23