Submission #541348

#	Time	Username	Problem	Language	Result	Execution time	Memory
541348		mosiashvililuka	Teams (IOI15_teams)	C++14	0 / 100	600 ms	203432 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];
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>=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;
	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 qw=0,we=0;
	qw=lower_bound(p+1,p+b+1,make_pair(q,0))-p;
	we=lower_bound(p+1,p+b+1,make_pair(w+1,0))-p-1;
	if(qw+1>we) return a+3;
	l=1;r=w-1;z=0;
	read(1,za,1,qw+1,b);
	K=z+dp[q]-dp[w];
	z=0;
	read2(1,za,1,qw+1,we);
	if(K>0){
		return a+3;
	}
	return z;
}
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(p[i].second);
	}
	bld(1,za,1);
}
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;
	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(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[j],f[i])+(k[f[i]]-f[i]*g[i]);
			if(dp[i]>zx) dp[i]=zx;
		}
	}
	zx=0;
	for(i=1; i<=a; i++){
		zx=min(zx,dp[i]);
	}
	if(zx>=0) return 1; else return 0;
}

Compilation message (stderr)

teams.cpp: In function 'void bld(int, int, int)':
teams.cpp:16:10: warning: declaration of 'h' shadows a global declaration [-Wshadow]
   16 |  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:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int h=1; h<v[rr].size(); h++){
      |               ~^~~~~~~~~~~~~
teams.cpp: In function 'int W(int, int)':
teams.cpp:55:42: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   55 |  qw=lower_bound(p+1,p+b+1,make_pair(q,0))-p;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:56:46: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   56 |  we=lower_bound(p+1,p+b+1,make_pair(w+1,0))-p-1;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp: In function 'int cost(int, int)':
teams.cpp:70:46: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   70 |  qw=lower_bound(p+1,p+b+1,make_pair(q+1,0))-p-1;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

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