Submission #1210702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210702		nguyn	Fountain (eJOI20_fountain)	C++20	100 / 100	216 ms	34044 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 2e5 + 5;

int n, q; 
int d[N], c[N], r[N], v[N];
vector<int> g[N]; 
int up[N][20];
int sum[N][20];

void dfs(int u) {
	for (int v : g[u]) {
		// cout << v << ' ' << u << endl;
		up[v][0] = u;
		sum[v][0] = c[v]; 
		for (int i = 1; i < 20; i++) {
			up[v][i] = up[up[v][i - 1]][i - 1];
			sum[v][i] = sum[up[v][i - 1]][i - 1] + sum[v][i - 1]; 
		}
		dfs(v);
	}
}

int jump(int u, int x) {
	for (int i = 19; i >= 0; i--) {
		if (sum[u][i] < x) {
			x -= sum[u][i]; 
			u = up[u][i];
		}	
	}
	if (u == n + 1) return 0; 
	return u;
}

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
    	cin >> d[i] >> c[i];
    }
    for (int i = 1; i <= q; i++) {
    	cin >> r[i] >> v[i];
    }
    stack<int> st;
    st.push(n + 1);
    d[n + 1] = 1e9 + 6;
    c[n + 1] = 1e9 + 6;
    for (int i = n; i >= 1; i--) {
    	while(!st.empty() && d[i] >= d[st.top()]) st.pop(); 
    	g[st.top()].pb(i); 
    	// cout << st.top() << ' ' << i << '\n';
    	st.push(i); 
    }	
    for (int i = 0; i < 20; i++) sum[n + 1][i] = c[n + 1]; 
    dfs(n + 1);
    // for (int i = 1; i <= n; i++) {
    // 	for (int j = 0; j < 3; j++) {
    // 		cout << sum[i][j] << ' ';
    // 	} cout << '\n';
    // } 
    for (int i = 1; i <= q; i++) {
    	cout << jump(r[i], v[i]) << '\n'; 
    }
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40