oj.uz

Submission #699956

# Submission time Handle Problem Language Result Execution time Memory
699956 2023-02-18T11:52:50 Z Nuraly_Serikbay Fountain (eJOI20_fountain) C++14
100 / 100
 358 ms 44636 KB 
//#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

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 728 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 35984 KB Output is correct
2 Correct 250 ms 33640 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 728 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 218 ms 35984 KB Output is correct
9 Correct 250 ms 33640 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 94 ms 21472 KB Output is correct
12 Correct 358 ms 39216 KB Output is correct
13 Correct 254 ms 39276 KB Output is correct
14 Correct 187 ms 38224 KB Output is correct
15 Correct 166 ms 44636 KB Output is correct