oj.uz

Submission #407286

# Submission time Handle Problem Language Result Execution time Memory
407286 2021-05-18T17:23:15 Z drkarlicio2107 Fountain (eJOI20_fountain) C++14
0 / 100
 89 ms 34616 KB 
#include <bits/stdc++.h>
using namespace std; int par [100010]; vector <int> ch [100010]; long long int pro  [100010]; long long int kap [100010];
int LCA [100010][20]; stack < pair <long long int, int> > s; long long int inf=1e18;
long long int pref [100010];
void calc (long long int tonow, int node){
	for (int i=0; i<ch[node].size(); i++) calc (tonow+kap[node], ch[node][i]);
	pref[node]=tonow+kap[node];
	return ;
}
int main(){
	int n,q; cin >> n >> q;
	for (int i=0; i<n; i++){
		cin >> pro[i] >> kap [i];
	}
	//building tree
	par [n]=-1; s.push (make_pair (inf, n)); kap [n]=inf;
	for (int i=n-1; i>=0; i--){
		int x;
		while (s.top().first<=pro[i]) s.pop();
		x=s.top().second; s.push (make_pair(pro[i], i));
		par [i]=x; ch [x].push_back(i);
	}
	//building LCA
	for (int i=0; i<n+1; i++) LCA [i][0]=par [i];
	for (int j=1; j<20; j++){
		for (int i=0; i<n+1; i++){
			LCA [i][j]=LCA [LCA[i][j-1]][j-1];
		}
	}
	cout << endl;
	//making prefix
	calc (0, n);
	//answering queryes
	for (int i=0; i<q; i++){
		int poc; long long int val; cin >> poc >> val; poc--; int x=poc;
		while (1) {
			if (x==n) break;
			if (pref[poc]-pref[LCA[x][0]]>=val) break;
			if (par[par[x]]==-1 || pref[poc]-pref[LCA[x][1]]>=val){
				x=par[x]; break;
			}
			for (int j=1; j<20; j++){
				int now=LCA[x][j];
				cout << now << endl;
				if (now==-1 || par[now]==-1 || LCA[now][0]==-1){
					x=n; break;
				}
				if (pref[poc]-pref[par[now]]>=val){
					x=LCA[x][j-1]; break;
				}
			}
		}
		if (x!=n) cout << x+1 << endl;
		else cout << 0 << endl;
	}
	return 0;
}

Compilation message

fountain.cpp: In function 'void calc(long long int, int)':
fountain.cpp:6:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |  for (int i=0; i<ch[node].size(); i++) calc (tonow+kap[node], ch[node][i]);
      |                ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 34616 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -