Submission #541417

#	Time	Username	Problem	Language	Result	Execution time	Memory
541417		mosiashvililuka	Teams (IOI15_teams)	C++14	56 / 100	1217 ms	206852 KiB

teams

#include<bits/stdc++.h>
#include "teams.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[500009],dp[500009],k[500009],za,l,r,z,zz,g[500009],G[500009],K;
pair <int, int> p[500009];
multiset <int> s;
multiset <int>::iterator it,tt,TT;
multiset <pair <int, int> > h;
multiset <pair <int, int> >::iterator IT;
vector <int> v[1200009],pr[1200009];
int cost(int q, int w);
void bld(int q, int w, int rr){
	if(q>=w) return;
	int mid=(q+w)/2;
	pr[rr].resize(v[rr].size());
	v[rr*2].push_back(0);v[rr*2+1].push_back(0);
	for(int h=1; h<v[rr].size(); h++){
		pr[rr][h]=pr[rr][h-1];
		if(p[v[rr][h]].second<=mid){
			pr[rr][h]++;
			v[rr*2].push_back(v[rr][h]);
		}else{
			v[rr*2+1].push_back(v[rr][h]);
		}
	}
	bld(q,mid,rr*2);
	bld(mid+1,w,rr*2+1);
}
void read(int q, int w, int rr, int L, int R){
	if(q>w) return;
	if(L>R) return;
	if(q>r||w<l) return;
	//cout<<q<<" "<<w<<" "<<rr<<" "<<L<<" "<<R<<"\n";
	if(q>=l&&w<=r){
		z+=R-L+1;
		return;
	}
	read(q,(q+w)/2,rr*2,pr[rr][L-1]+1,pr[rr][R]);
	read((q+w)/2+1,w,rr*2+1,((L-1)-pr[rr][L-1])+1,(R-pr[rr][R]));
}
void read2(int q, int w, int rr, int L, int R){
	if(q>w||L>R||K<=0) return;
	//cout<<q<<" "<<w<<" "<<rr<<" "<<L<<" "<<R<<"\n";
	if(R-L+1<K){
		K-=R-L+1;
		z=p[v[rr][R]].second;
		return;
	}
	if(q==w){
		z=q;K=0;
		return;
	}
	read2(q,(q+w)/2,rr*2,pr[rr][L-1]+1,pr[rr][R]);
	read2((q+w)/2+1,w,rr*2+1,((L-1)-pr[rr][L-1])+1,(R-pr[rr][R]));
}
int W(int q, int w){
	//if(dp[q]<=dp[w]) return 0;
	int AS=0,SD=0;
	AS=dp[q];SD=dp[w]-k[f[w]]+cost(f[q],f[w]);
	//cout<<AS<<" "<<SD<<"\n";
	if(AS<=SD) return 0;
	int qw=0,we=0;
	qw=lower_bound(p+1,p+b+1,make_pair(f[q]+1,0))-p;
	we=lower_bound(p+1,p+b+1,make_pair(f[w]+1,0))-p-1;
	if(qw>we) return b+3;
	//cout<<q<<" "<<w<<"  "<<qw<<" "<<we<<"\n";
	l=1;r=f[w]-1;z=0;
	//cout<<l<<" "<<r<<"   "<<qw<<" "<<b<<"\n";
	read(1,za,1,qw,b);
	//cout<<z<<"\n";
	//exit(0);
	//K=z+dp[q]-dp[w];
	K=z+AS-SD;
	z=0;
	read2(1,za,1,qw,we);
	if(K>0){
		return b+3;
	}
	return z+1;
}
int cost(int q, int w){
	int qw=0;
	qw=lower_bound(p+1,p+b+1,make_pair(q+1,0))-p-1;
	if(qw<=0) return 0;
	l=w;r=b;z=0;
	read(1,za,1,1,qw);
	return z;
}
void init(int Nn, int Aa[], int Bb[]) {
	b=Nn;
	for(i=1; i<=b; i++){
		p[i].first=Aa[i-1];p[i].second=Bb[i-1];
		k[p[i].first]++;k[p[i].second+1]--;
	}
	for(i=1; i<=b; i++) k[i]+=k[i-1];
	sort(p+1,p+b+1);
	za=1;
	while(za<b) za*=2;
	v[1].push_back(0);
	for(i=1; i<=b; i++){
		v[1].push_back(i);
	}
	bld(1,za,1);
}
void print(){
	cout<<dp[1]<<" "<<dp[2]<<" "<<dp[3]<<"\n";
	cout<<"s: ";
	for(it=s.begin(); it!=s.end(); it++){
		cout<<(*it)<<" ";
	}
	cout<<"\n";
	cout<<"h: ";
	for(IT=h.begin(); IT!=h.end(); IT++){
		cout<<(*IT).first<<" "<<(*IT).second<<"   ";
	}
	cout<<"\n";
}
int can(int Mm, int Kk[]) {
	a=Mm;zx=0;
	for(i=1; i<=a; i++){
		G[i]=Kk[i-1];zx+=G[i];
	}
	sort(G+1,G+a+1);
	if(zx>b){
		return 0;
	}
	c=0;
	for(i=1; i<=a; i++){
		if(f[c]==G[i]){
			g[c]++;
		}else{
			c++;f[c]=G[i];g[c]=1;
		}
	}
	a=c;
	
	//
	/*cout<<a<<endl;
	for(i=1; i<=a; i++){
		cout<<f[i]<<" "<<g[i]<<"\n";
	}*/
	
	
	//
	//cout<<"cost: "<<cost(3,5)<<"\n";
	
	//
	
	dp[1]=-1;dp[2]=0;
	//cout<<W(1,2)<<"\n";
	//exit(0);
	//
	
	s.clear();h.clear();
	for(i=1; i<=a; i++){
		dp[i]=k[f[i]]-f[i]*g[i];
		e=0;
		if(s.size()!=0){
			it=s.end();it--;
			if(W((*it),i-1)<=i){
				e=1;
			}
		}
		if(i==1) e=1;
		if(e==0){
			s.insert(i-1);
			if(s.size()>1){
				it=s.end();it--;it--;
				c=W((*it),i-1);
				h.insert({c,(*it)});
			}
		}
		
		while(h.size()){
			IT=h.begin();
			if((*IT).first>i) break;
			it=s.lower_bound((*IT).second);tt=it;tt++;
			h.erase(IT);
			TT=tt;TT++;
			if(TT!=s.end()){
				c=W((*tt),(*TT));
				h.erase(h.lower_bound({c,(*tt)}));
				c=W((*it),(*TT));
				h.insert({c,(*it)});
			}
			s.erase(tt);
		}
		if(s.size()!=0){
			it=s.end();it--;
			zx=dp[(*it)]-cost(f[(*it)],f[i])+(k[f[i]]-f[i]*g[i]);
			if(dp[i]>zx) dp[i]=zx;
		}
		/*if(i==3){
			cout<<dp[1]<<" "<<dp[2]<<" "<<dp[3]<<"\n";
			cout<<"s: ";
			for(it=s.begin(); it!=s.end(); it++){
				cout<<(*it)<<" ";
			}
			cout<<"\n";
			cout<<"h: ";
			for(IT=h.begin(); IT!=h.end(); IT++){
				cout<<(*IT).first<<" "<<(*IT).second<<"   ";
			}
			cout<<"\n";
			exit(0);
		}*/
	}
	zx=0;
	for(i=1; i<=a; i++){
		zx=min(zx,dp[i]);
	}
	/*for(i=1; i<=a; i++) cout<<dp[i]<<" ";
	cout<<"\n";*/
	if(zx>=0) return 1; else return 0;
}

Compilation message (stderr)

teams.cpp: In function 'void bld(int, int, int)':
teams.cpp:17:10: warning: declaration of 'h' shadows a global declaration [-Wshadow]
   17 |  for(int h=1; h<v[rr].size(); h++){
      |          ^
teams.cpp:8:29: note: shadowed declaration is here
    8 | multiset <pair <int, int> > h;
      |                             ^
teams.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int h=1; h<v[rr].size(); h++){
      |               ~^~~~~~~~~~~~~
teams.cpp: In function 'int W(int, int)':
teams.cpp:63:47: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   63 |  qw=lower_bound(p+1,p+b+1,make_pair(f[q]+1,0))-p;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:64:49: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   64 |  we=lower_bound(p+1,p+b+1,make_pair(f[w]+1,0))-p-1;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp: In function 'int cost(int, int)':
teams.cpp:83:46: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   83 |  qw=lower_bound(p+1,p+b+1,make_pair(q+1,0))-p-1;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

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