oj.uz

Submission #383217

# Submission time Handle Problem Language Result Execution time Memory
383217 2021-03-29T08:38:13 Z MODDI Fountain (eJOI20_fountain) C++14
30 / 100
 1500 ms 2344 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, q;
vector<pii> arr;
int parent[100000], water[100000];
int main(){
	cin>>n>>q;
	bool sorted = true;
	for(int i = 0; i < n; i++){
		int a, b;
		cin>>a>>b;
		if(i > 0 && arr[arr.size() - 1].first < a)
			sorted = false;
		arr.pb(mp(a,b));
		water[i] = b;
	}
	if(sorted){
		vi pref;
		pref.pb(water[0]);
		for(int i = 1; i < n; i++)
			pref.pb(water[i] + pref[i - 1]);
		while(q--){
			int at, vol;
			cin>>at>>vol;
			at--;
			int l = 0, r = n - 1, mid;
			while(l <= r){
				mid = (l + r) / 2;
				if(water[mid] < vol)
					l = mid + 1;
				else
					r = mid - 1;
			}
			cout<<l<<" "<<mid+1<<endl;
		}
		return 0;
	}
	for(int i = 0; i < n; i++){
		bool f = false;
		for(int j = i + 1; j < n; j++){
			if(arr[i].first < arr[j].first)
			{
				f = true;
				parent[i] = j;
				break;
			}
			else
				continue;
		}
		if(!f)
		parent[i] = n;
		//cout<<"the parent of "<<i<<" is "<<parent[i]<<endl;
	}
	while(q--){
		int at, vol;
		cin>>at>>vol;
		at--;
		if(vol <= water[at])
		{
			cout<<at + 1<<endl;
			continue;
		}
		while(vol > 0){
			if(at == n){
				cout<<0<<endl;
				break;
			}
			if(vol - water[at] <= 0){
				cout<<at + 1<<endl;
				break;
			}
			vol -= water[at];
			at = parent[at];
		}
	}
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:41:22: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |    cout<<l<<" "<<mid+1<<endl;
      |                      ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 6 ms 364 KB Output is correct
5 Correct 11 ms 492 KB Output is correct
6 Correct 8 ms 364 KB Output is correct
7 Correct 7 ms 364 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 2344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 6 ms 364 KB Output is correct
5 Correct 11 ms 492 KB Output is correct
6 Correct 8 ms 364 KB Output is correct
7 Correct 7 ms 364 KB Output is correct
8 Execution timed out 1589 ms 2344 KB Time limit exceeded
9 Halted 0 ms 0 KB -