oj.uz

Submission #914655

# Submission time Handle Problem Language Result Execution time Memory
914655 2024-01-22T13:25:58 Z schzeey Fountain (eJOI20_fountain) C++14
30 / 100
 1008 ms 524288 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 4 ms 856 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 12 ms 7772 KB Output is correct
6 Correct 9 ms 3420 KB Output is correct
7 Correct 5 ms 344 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1008 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 4 ms 856 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 12 ms 7772 KB Output is correct
6 Correct 9 ms 3420 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Runtime error 1008 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -