Submission #58254

#	Time	Username	Problem	Language	Result	Execution time	Memory
58254		WA_TLE	Teams (IOI15_teams)	C++14	100 / 100	2915 ms	119840 KiB

teams

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
//#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1e9+7;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
//llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
//segment treeをうまく使ってO(nlogn+mlog^2n)
//うまくやればO(n^(1+1/k) logn+kmlogm)
//累積和の使用
//IOI2015 teams 77pot answer?
//「B人以下」をうまくsegment treeに乗せる
//can
//stackを使ってうまくする
//524288
//1048576 mre?
//I'm tourist!!という強い気持ちを持って生きていこう
#include<teams.h>
vector<int>seg[1048576];
int n;
vector<int>hito;
void init(int N,int A[],int B[]){
	n=N;
	int i;
	hito.res(n+1);
	for(i=0;i<n;i++){hito[i]=B[i]*10;}
	SO(hito);
	for(i=0;i<n;i++){
		int bas=LBI(hito,B[i]*10);
		seg[(1<<19)+bas].pub(A[i]);
		hito[bas]--;//出てこないようにしている
	}
	for(i=0;i<=n;i++){hito[i]++;hito[i]/=10;}//もとに戻している
	for(i=1;i<=n;i++){SO(seg[(1<<19)+i]);}
	for(i=(1<<19)-1;i>0;i--){
		merge(seg[i+i].begin(),seg[i+i].end(),seg[i+i+1].begin(),seg[i+i+1].end(),back_inserter(seg[i]));
		//マージソートでlogを削減★
	}
}
//Bがここからここまでの間にAが小さいほうから何人 にlog(n)^2で　答える
int can(int M,int K[]){
	vector<tuple<int,int>>sta;
	//A値がそれ以下、B値がそれ未満のが全部使われた
	sta.pub(mt(-1,520000));
	sort(K,K+M);
	//セグ木上の二分探索
	int i;
	for(i=0;i<M;i++){
		int team=K[i];
		int noko=K[i];//残り人数
		int mita=LBI(hito,K[i]);//mita未満のB値はいらない
		while(-1){
			if(sta.empty()&&noko==0){break;}
			if(sta.empty()){return 0;}//人を使い切ってしまった、game over
			int mae=get<0>(sta.back());
			int doco=get<1>(sta.back());
			//cerr<<"doco="<<doco<<"mita="<<mita<<endl;
			if(doco<=mita){sta.pob();continue;}
			//まずはセグ木上の二分探索する前にstackがどうかを考える
			int iru=0;
			//Bがmita以上、doco未満の区間について
			//Aがmaeより上,team以下の区間について、
			//そこにいる人たちがnoko人より大きい->break
			//else->sta.pop;
			int biL=(1<<19)+mita-1;
			int biR=(1<<19)+doco;
			while(biL+1<biR){
				if(biL%2==0){iru+=UBI(seg[biL+1],team)-UBI(seg[biL+1],mae);}
				if(biR%2==1){iru+=UBI(seg[biR-1],team)-UBI(seg[biR-1],mae);}
				biL/=2;biR/=2;
			}
			//cerr<<"iru="<<iru<<endl;
			if(noko<iru){break;}
			else{mita=doco;noko-=iru;sta.pob();}//2つを合わせる
		}
		//mita以上の部分で、
		//Bがmita以上、x未満の区間について,
		//Aがmae以上,team以下の区間について、
		//そこにいる人たちが目標人になるようなxをセグ木上の二分探索
		//Bがmita未満をnokoに足す
		int mae=get<0>(sta.back());
		int doco=get<1>(sta.back());
		int biR=(1<<19)+mita;
		while(biR>1){
			if(biR%2==1){noko+=UBI(seg[biR-1],team)-UBI(seg[biR-1],mae);}
			biR/=2;
		}
		//セグ木上の二分探索
		biR=1;
		while(biR<(1<<19)){
			biR*=2;
			int nin=UBI(seg[biR],team)-UBI(seg[biR],mae);
			if(noko>=nin){biR++;noko-=nin;}
		}
		sta.pub(mt(team,biR-(1<<19)));
		//for(auto it:sta){cerr<<"de "<<get<0>(it)<<" "<<get<1>(it)<<endl;}
		//cerr<<"aaa"<<endl;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:73:14: warning: conversion to 'int' from 'llint {aka long long int}' may alter its value [-Wconversion]
   int bas=LBI(hito,B[i]*10);
           ~~~^~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:95:15: warning: conversion to 'int' from 'llint {aka long long int}' may alter its value [-Wconversion]
   int mita=LBI(hito,K[i]);//mita未満のB値はいらない
            ~~~^~~~~~~~~~~
teams.cpp:112:62: warning: conversion to 'int' from 'llint {aka long long int}' may alter its value [-Wconversion]
     if(biL%2==0){iru+=UBI(seg[biL+1],team)-UBI(seg[biL+1],mae);}
                                                              ^
teams.cpp:113:62: warning: conversion to 'int' from 'llint {aka long long int}' may alter its value [-Wconversion]
     if(biR%2==1){iru+=UBI(seg[biR-1],team)-UBI(seg[biR-1],mae);}
                                                              ^
teams.cpp:129:62: warning: conversion to 'int' from 'llint {aka long long int}' may alter its value [-Wconversion]
    if(biR%2==1){noko+=UBI(seg[biR-1],team)-UBI(seg[biR-1],mae);}
                                                              ^
teams.cpp:136:30: warning: conversion to 'int' from 'llint {aka long long int}' may alter its value [-Wconversion]
    int nin=UBI(seg[biR],team)-UBI(seg[biR],mae);
            ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
teams.cpp:126:7: warning: unused variable 'doco' [-Wunused-variable]
   int doco=get<1>(sta.back());
       ^~~~

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