CSAcademy Round #75 : D. Electric Cars

内容的には解ける問題だったのに時間切れでダメだったのもったいない。
https://csacademy.com/contest/round-75/task/electric-cars/

問題

N台の電気自動車がそれぞれ時刻T[i]にガソリンスタンドにやってくる。
各自動車の充電時間はC[i]かかる。

ガソリンスタンドは、時刻1毎にその時点でガソリンスタンドにいる車の中で最も番号の若いものにその間充電する。
新しい自動車が来ることで、充電順が入れ替わることもある。
各自動車の充電完了時刻を答えよ。

解法

新たな自動車が来るまでは、今いる充電未完の自動車に先頭から順に充電していくことになる。

ガソリンスタンドで充電待ちの車の集合を管理しよう。
新たな自動車が来るタイミングで、その前に自動車来た時刻との差分の間、番号の若い順に順に充電していけばよい。
車の追加と充電完了による集合の削除がたまに1回ずつなので、車の集合をsetで管理しても均しO(N logN)で済む。

int N;
int C[101010],T[101010];
ll ret[101010];
vector<pair<ll,int>> E;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>C[i]>>T[i];
		E.push_back({T[i],i});
	}
	E.push_back({1LL<<60,N});
	
	set<int> S;
	sort(ALL(E));
	ll pre=0;
	FORR(e,E) {
		ll dif=e.first-pre;
		while(dif>0 && S.size()) {
			x=*S.begin();
			
			if(C[x]<=dif) {
				ret[x]=pre+C[x];
				pre+=C[x];
				dif-=C[x];
				S.erase(S.begin());
			}
			else {
				C[x]-=dif;
				dif=0;
			}
		}
		pre=e.first;
		S.insert(e.second);
	}
	
	FOR(i,N) cout<<ret[i]<<endl;
}

まとめ

まぁこちらはあまり手こずらなかった。