#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 + 1);
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
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 time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
340 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
524 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
2828 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
340 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
524 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
