# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
963520 | 2024-04-15T08:59:07 Z | ONEHUNDREDPUSHUPS | Fountain (eJOI20_fountain) | C++17 | 274 ms | 43880 KB |
#include<bits/stdc++.h> #define sz size() #define ll long long #define t s.begin() using namespace std; const ll N = 100100; const ll INF = 1e18; ll up[N][20], sum[N][20]; void solve() { ll n, q, i, j, k; cin >> n >> q; vector<ll> d(n + 5, INF), c(n + 5, INF); for(i = 1; i <= n; ++i) { cin >> d[i] >> c[i]; } set<pair<ll, int>> s; for(i = 1; i <= n; ++i) { while(s.sz && (*t).first < d[i]) { up[(*t).second][0] = i; s.erase(t); } s.insert({d[i], i}); } for(i = n; i >= 1; --i) { sum[i][0] = c[up[i][0]]; for(j = 1; j < 20; ++j) up[i][j] = up[up[i][j - 1]][j - 1], sum[i][j] = sum[i][j - 1] + sum[up[i][j - 1]][j - 1]; } // for(i = 1; i <= n; ++i) // cout << up[i][0] << ' '; // return; while(q--) { ll r, v; cin >> r >> v; v -= c[r]; for(j = 19; j >= 0; --j) { if(sum[r][j] && sum[r][j] <= v) { v -= sum[r][j]; r = up[r][j]; } } if(v > 0) r = up[r][0]; cout << r << '\n'; } } signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2408 KB | Output is correct |
4 | Correct | 2 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 1 ms | 2652 KB | Output is correct |
7 | Correct | 2 ms | 2652 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 179 ms | 36528 KB | Output is correct |
2 | Correct | 191 ms | 36692 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2408 KB | Output is correct |
4 | Correct | 2 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 1 ms | 2652 KB | Output is correct |
7 | Correct | 2 ms | 2652 KB | Output is correct |
8 | Correct | 179 ms | 36528 KB | Output is correct |
9 | Correct | 191 ms | 36692 KB | Output is correct |
10 | Correct | 2 ms | 2648 KB | Output is correct |
11 | Correct | 56 ms | 24404 KB | Output is correct |
12 | Correct | 274 ms | 38564 KB | Output is correct |
13 | Correct | 167 ms | 38640 KB | Output is correct |
14 | Correct | 111 ms | 37456 KB | Output is correct |
15 | Correct | 100 ms | 43880 KB | Output is correct |