Submission #699956

#	Time	Username	Problem	Language	Result	Execution time	Memory
699956		Nuraly_Serikbay	Fountain (eJOI20_fountain)	C++14	100 / 100	358 ms	44636 KiB

fountain

//#include <bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>

using namespace std;

#define int long long
#define pb push_back
#define S second
#define F first

const int N = 2e5 + 5;
const int INF = 1e18 - 1;
const int MOD = 1e9 + 7;

int n, d[N];
int q, dp[N][21], g[N][21];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    int ok = 0;
    for (int i = 1; i <= n; ++ i) cin >> d[i] >> dp[i][0];    
   	
    set <pair <int, int>> s;
    
    for (int i = 1; i <= n; ++ i) {
    	while (s.size() && (*s.begin()).F < d[i]) {
    		g[(*s.begin()).S][0] = i;
    		s.erase (s.begin());
    	}
    	s.insert ({d[i], i});
    }
    
    for (int i = 1; i <= 20; ++ i) {
    	for (int j = 1; j <= n; ++ j) {
    		g[j][i] = g[g[j][i - 1]][i - 1];
    		dp[j][i] = dp[j][i - 1] + dp[g[j][i - 1]][i - 1];
    	}
    }
    while (q --) {
    	int pos, val;
    	cin >> pos >> val;
    	for (int i = 19; i >= 0; -- i) {
    		if (dp[pos][i] >= val) continue;
    	//	cout << i << ' ';
    		val -= dp[pos][i];
    		if (val) pos = g[pos][i];
    	}
    //	cout << '\n';
    	cout << pos << '\n';
    }
    
    
    
   	return 0;
}
/*
6 1
4 10
6 8
3 5
4 14
10 9
4 20
2 8
 

*/

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:47:9: warning: unused variable 'ok' [-Wunused-variable]
   47 |     int ok = 0;
      |         ^~

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