oj.uz

Submission #467282

# Submission time Handle Problem Language Result Execution time Memory
467282 2021-08-22T12:03:14 Z mansur Fountain (eJOI20_fountain) C++17
30 / 100
 276 ms 35976 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<pii> s;
	for (int i = 1; i <= n; i++) {
		cin >> d[i] >> c[i];
		s.pb({d[i], i});
	}
	sort(rall(s));
	set<int> pos;
	pos.insert(n + 1);
	for (auto e: s) {
		auto it = pos.upper_bound(e.ss);
		pos.insert(e.ss);
		r[e.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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 35976 KB Output is correct
2 Correct 276 ms 33304 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -