Submission #615446

#TimeUsernameProblemLanguageResultExecution timeMemory
615446ArsBudFountain (eJOI20_fountain)C++14
0 / 100
19 ms2284 KiB
#include <iostream> using namespace std; int N, Q, k, y = 0, n, v, vid, r; int m[200005], i[100005], t[100005]; void F(int x) { // cout << "y = " << y << ", x = " << x << ", i[y] = " << i[y] << ", i[x] = " << i[x] << ", m[y] = " << m[y] << ", m[x] = " << m[x] << '\n'; if(i[y] < i[x]) { m[y] = x; return; } if(m[y] > 0 || m[x] <= 0) { if(x == N) { m[y] = -1; } return; } F(m[x]); } void F1(int w) { // cout << "w = " << w << ", v = " << v << ", t[w] = " << t[w] << ", n = " << n << '\n'; if(t[w] >= v) { v = 0; n = w; return; } if(v > t[w] && m[w] == -1) { n = -1; return; } v -= t[w]; // cout << "v = " << v << ", m[w] = " << m[w] << '\n'; F1(m[w]); } int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); cin >> N >> Q; r = N / 2; int g; for(int a = 0; a < N; a++) { cin >> i[a] >> t[a]; if(i[a] > i[a - 1]) { g++; } } // cout << "g == N\n"; if(g == N) { t[-1]= 0; // cout << "t[-1] = " << t[-1] << '\n'; for(int a = 0; a < N; a++) { t[a] += t[a - 1]; } for(int a = 0; a < Q; a++) { // cout << "a = " << a << '\n'; int e, h; // cout << "e = " << e << ", h = " << h << '\n'; cin >> e >> h; // cout << "e = " << e << ", h = " << h << '\n'; vid = h - 1; r = h / 2; // cout << "vid = " << vid << ", r = " << r << ", e = " << e << '\n'; while(e > 0) { // cout << "e = " << e << ", t[vid] = " << t[vid] << '\n'; if(t[vid] > e) { vid -= max(1, r / 2); // cout << "vid = " << vid << ", n = " << n << ", t[n] = " << t[n] << '\n'; if(vid < h - 1 && e < t[h - 1]) { // cout << h << '\n'; break; } else { vid = h - 1; } } if(t[vid] < e) { vid += max(1, r / 2); } if(t[vid] >= e && t[vid - 1] < e) { // cout << vid + 1 << '\n'; break; } if(t[vid] < e && vid >= N - 1) { // cout << 0 << '\n'; break; } } } return 0; } m[N - 1] = -1; for(int a = N - 2; a >= 0; a--) { // cout << "a = " << a << ", i[a] = " << i[a] << ", i[a + 1] = " << i[a + 1] << '\n'; if(i[a] < i[a + 1]) { m[a] = a + 1; // cout << "m[a] = " << m[a] << '\n'; } else { y = a; F(a + 2); if(m[a] == 0) { m[a] = N - 1; } // cout << "m[a] = " << m[a] << '\n'; } } // cout << "ATS : \n"; for(int a = 0; a < Q; a++) { cin >> n >> v; n--; F1(n); // cout << "GRIZO\n"; if(v < 0) { cout << 0 << '\n'; } else { cout << n + 1 << '\n'; } } // for(int a = 0; a < N; a++) // { // cout << "a = " << a << ", m[a] = " << m[a] << '\n'; // } return 0; }

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:65:13: warning: array subscript -1 is below array bounds of 'int [100005]' [-Warray-bounds]
   65 |         t[-1]= 0;
      |         ~~~~^
fountain.cpp:6:27: note: while referencing 't'
    6 | int m[200005], i[100005], t[100005];
      |                           ^
fountain.cpp:63:5: warning: 'g' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     if(g == N)
      |     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...