oj.uz

Submission #813533

# Submission time Handle Problem Language Result Execution time Memory
813533 2023-08-07T19:48:15 Z Acanikolic Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 41744 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 = 1e5+10;
		 
const int mod = 1e9+7;
		 
const int inf = 1e18;	

const int lg = 18;

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 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 39596 KB Output is correct
2 Correct 205 ms 36600 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 214 ms 39596 KB Output is correct
9 Correct 205 ms 36600 KB Output is correct
10 Correct 2 ms 3028 KB Output is correct
11 Correct 919 ms 22160 KB Output is correct
12 Correct 346 ms 41744 KB Output is correct
13 Execution timed out 1591 ms 36728 KB Time limit exceeded
14 Halted 0 ms 0 KB -