Submission #914655

#	Time	Username	Problem	Language	Result	Execution time	Memory
914655		schzeey	Fountain (eJOI20_fountain)	C++14	30 / 100	1008 ms	524288 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>

struct tp{
	int pref_c;
	int ind;
	int dia;
};

unordered_map<int, vector<tp>> tr;
	
int bns (int r, int v){
	vector <tp> cur = tr[r];
	int lf = 0, ri = cur.size()-1;
	if (v >cur[ri].pref_c) return 0;
	while (lf <= ri){
		int mid = (lf + ri)/2;
		if (cur[mid].pref_c >= v) ri = mid - 1;
		else lf = mid+1; 	
	}
	return cur[lf].ind;
}

int main(){
	int n, q; cin >> n >> q;
	
	for (int i = 1; i <= n; ++i){
		int a, b; cin >> a >> b; // diameter, capacity
		tp cur;
		cur.ind = i; cur.dia = a;
		for(auto it = tr.begin(); it != tr.end(); ++it){
			//tp move = now.second.back();
			tp now = it->second.back();
			if (now.dia < cur.dia){
				cur.pref_c = now.pref_c + b;
				tr[it->first].push_back(cur);
			}
		
		}
		cur.pref_c = b;
		tr[i].push_back(cur);
	}
	/*for (auto p: tr){
		cout << p.first << ": ";
		for (tp k: p.second) cout << k.pref_c << " " << k.ind << " " << k.dia << endl;
		cout << endl;
	}*/
	for (int i = 0; i < q; ++i){
		int r, v; cin >> r >> v;
		cout << bns (r, v) << endl;
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40