oj.uz

Submission #467300

# Submission time Handle Problem Language Result Execution time Memory
467300 2021-08-22T12:41:52 Z mansur Fountain (eJOI20_fountain) C++17
100 / 100
 378 ms 39100 KB 
#include<bits/stdc++.h>	
 
#pragma optimize ("g",on)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
             		
using namespace std;
 
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define pb push_back
#define nl '\n'
#define popb pop_back()
#define sz size()
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second  
#define fix fixed << setprecision
#define pii pair<int, int>
#define E exit (0)
#define int long long
 
const int inf = (1ll << 62ll), N = 1e5 + 2, mod = 1e9 + 7;                    
 
vector<pii> dd = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

pii up[N][18];

signed main() {
	//freopen("invtrans.in", "r", stdin);
	//freopen("invtrans.out", "w", stdout);
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	int n, q;
	cin >> n >> q;
	int d[n + 1], c[n + 1], r[n + 1];
	vector<pair<int, pii>> s;
	for (int i = 1; i <= n; i++) {
		cin >> d[i] >> c[i];
		s.pb({d[i], {n - i, i}});
	}
	sort(rall(s));
	set<int> pos;
	pos.insert(n + 1);
	for (auto e: s) {
		auto it = pos.upper_bound(e.ss.ss);
		pos.insert(e.ss.ss);
		r[e.ss.ss] = *it;	
	}
	for (int i = 1; i <= n; i++) {
		up[i][0] = {r[i], c[i]};	
	}

	up[n + 1][0] = {n + 1, 0};
	for (int j = 1; j < 18; j++) {
		for (int i = 1; i <= n + 1; i++) {
			up[i][j] = {up[up[i][j - 1].ff][j - 1].ff, up[i][j - 1].ss + up[up[i][j - 1].ff][j - 1].ss};
		}
	}
	while (q--) {
		int rr, v;
		cin >> rr >> v;
		for (int i = 17; i >= 0; i--) {
			if (up[rr][i].ss >= v) continue;
			v -= up[rr][i].ss;
			rr = up[rr][i].ff;
		}
		cout << (rr == n + 1 ? 0 : rr) << nl;
	}
}

Compilation message

fountain.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize ("g",on)
      |

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 36788 KB Output is correct
2 Correct 283 ms 34100 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 259 ms 36788 KB Output is correct
9 Correct 283 ms 34100 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 112 ms 21656 KB Output is correct
12 Correct 378 ms 39064 KB Output is correct
13 Correct 297 ms 39100 KB Output is correct
14 Correct 213 ms 38956 KB Output is correct
15 Correct 175 ms 39072 KB Output is correct