# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
382837 | 2021-03-28T09:44:16 Z | aris12345678 | Fountain (eJOI20_fountain) | C++14 | 1500 ms | 2412 KB |
#include <bits/stdc++.h> using namespace std; const int mxN = 1e6+5; int diam[mxN], cap[mxN], pref[mxN]; int main() { int n, q; scanf("%d%d", &n, &q); for(int i = 1; i <= n; i++) { scanf("%d%d", &diam[i], &cap[i]); pref[i] = cap[i]+pref[i-1]; } if(is_sorted(diam+1, diam+n+1)) { while(q--) { int r, v; scanf("%d%d", &r, &v); int st = 1, en = n, ans, md; while(st <= en) { md = (st+en)/2; if(pref[md]-pref[r-1] < v) st = md+1; else ans = md, en = md-1; } if(pref[n]-pref[r-1] < v) printf("0\n"); else printf("%d\n", ans); } } else { while(q--) { int r, v; scanf("%d%d", &r, &v); int ans = 0, sum = 0, prev = r; for(int i = r; i <= n; i++) { if(diam[i] > diam[prev] || i == prev) { sum += cap[i], prev = i; if(sum >= v) { ans = i; break; } } } printf("%d\n", ans); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 2 ms | 364 KB | Output is correct |
4 | Correct | 2 ms | 364 KB | Output is correct |
5 | Correct | 2 ms | 364 KB | Output is correct |
6 | Correct | 4 ms | 364 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 90 ms | 2328 KB | Output is correct |
2 | Correct | 89 ms | 2412 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 2 ms | 364 KB | Output is correct |
4 | Correct | 2 ms | 364 KB | Output is correct |
5 | Correct | 2 ms | 364 KB | Output is correct |
6 | Correct | 4 ms | 364 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 90 ms | 2328 KB | Output is correct |
9 | Correct | 89 ms | 2412 KB | Output is correct |
10 | Correct | 2 ms | 364 KB | Output is correct |
11 | Execution timed out | 1572 ms | 2156 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |