이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (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());
^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |