# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1200484 | badge881 | Fountain (eJOI20_fountain) | C++20 | 130 ms | 16460 KiB |
#include <bits/stdc++.h>
using namespace std;
const int LOGK = 17, MAXN = 1e5 + 7;
int jump[MAXN][LOGK];
int suma[MAXN][LOGK];
int main(){
int n, q;
scanf("%d%d", &n, &q);
int a, b;
vector<pair<int, int>> tab;
for (int i = 0; i < n; i++){
scanf("%d%d", &a, &b);
tab.push_back({a, b});
}
tab.push_back({2e9, 2e9});
vector<int> stos;
stos.push_back(n);
for (int i = n - 1; i >= 0; i--){
while (tab[stos.back()].first <= tab[i].first)
stos.pop_back();
jump[i][0] = stos.back();
suma[i][0] = tab[stos.back()].second;
stos.push_back(i);
}
jump[n][0] = n;
for (int k = 1; k < LOGK; k++){
for (int v = 0; v <= n; v++){
jump[v][k] = jump[jump[v][k - 1]][k - 1];
if (jump[v][k] == n)
suma[v][k] = 2e9;
else
suma[v][k] = suma[v][k - 1] + suma[jump[v][k - 1]][k - 1];
}
}
while (q--){
scanf("%d%d", &a, &b);
a--;
int aktsuma = tab[a].second;
for (int k = LOGK - 1; k >= 0; k--){
if (jump[a][k] == n) continue;
if (aktsuma + suma[a][k] < b){
aktsuma += suma[a][k];
a = jump[a][k];
}
}
if (aktsuma < b)
a = jump[a][0];
if (a == n)
a = -1;
printf("%d\n", a + 1);
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |