oj.uz

Submission #813530

# Submission time Handle Problem Language Result Execution time Memory
813530 2023-08-07T19:44:36 Z Acanikolic Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 52156 KB 
#include <bits/stdc++.h>
		 		
#define int long long 
		 
#define pb push_back 
		
#define F first
		 
#define S second
		 
using namespace std;
		 
const int N = 3e5+10;
		 
const int mod = 1e9+7;
		 
const int inf = 1e18;	

const int lg = 20;

vector<int>g[N];
int up[N][lg],sm[N][lg],vis[N];
pair<int,int>a[N];

void dfs(int x,int par) {
	vis[x] = 1;
	for(auto X:g[x]) {
		if(X != par) {
			dfs(X,x);
		}
	}
}
				
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	
	int n,Q;
	cin >> n >> Q;
	for(int i=1;i<=n;i++) cin >> a[i].F >> a[i].S;
	stack<pair<int,int>>st;
	for(int i=1;i<=n;i++) up[i][0] = i;
	for(int i=n;i>=1;i--) {
		while(st.size() && st.top().F <= a[i].F) st.pop();
		if(!st.empty()) {
			g[i].pb(st.top().S);
			up[i][0] = st.top().S;
			sm[i][0] = a[st.top().S].S;
			// /cout << i << " -> " << st.top().S << ' ' << a[st.top().S].S << endl;
			//g[st.top().S].pb(i);
		}
		st.push({a[i].F,i});
	}
	for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);
	for(int j=1;j<lg;j++) {
		for(int i=1;i<=n;i++) {
			up[i][j] = up[up[i][j-1]][j-1];
			sm[i][j] = sm[i][j-1]+sm[up[i][j-1]][j-1];
		}
	}
	/*for(int i=1;i<=n;i++) {
		for(int j=0;j<lg;j++) cout << sm[i][j] << ' ';
		cout << endl;
	}*/
	while(Q--) {
		int index,val;
		cin >> index >> val;
		val -= a[index].S;
		for(int j=lg-1;j>=0;j--) {
			if(sm[index][j] <= val) {
				//cout << index << ' ' << j << ' ' << val << ' ' << sm[index][j] << endl;
				val -= sm[index][j];
				index = up[index][j];
			}
		}
		if(val > sm[index][0]) {
			cout << "0\n";
			continue;
		}
		if(val > 0) index = up[index][0];
		cout << index << '\n';
	}
    return 0; 
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7352 KB Output is correct
2 Correct 4 ms 7588 KB Output is correct
3 Correct 4 ms 7636 KB Output is correct
4 Correct 5 ms 7764 KB Output is correct
5 Correct 4 ms 7764 KB Output is correct
6 Correct 5 ms 7776 KB Output is correct
7 Correct 5 ms 7732 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 49628 KB Output is correct
2 Correct 217 ms 46696 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7352 KB Output is correct
2 Correct 4 ms 7588 KB Output is correct
3 Correct 4 ms 7636 KB Output is correct
4 Correct 5 ms 7764 KB Output is correct
5 Correct 4 ms 7764 KB Output is correct
6 Correct 5 ms 7776 KB Output is correct
7 Correct 5 ms 7732 KB Output is correct
8 Correct 203 ms 49628 KB Output is correct
9 Correct 217 ms 46696 KB Output is correct
10 Correct 4 ms 7764 KB Output is correct
11 Correct 920 ms 30332 KB Output is correct
12 Correct 324 ms 52156 KB Output is correct
13 Execution timed out 1578 ms 45552 KB Time limit exceeded
14 Halted 0 ms 0 KB -