#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
int N, Vmax, V2;
pii A[MAXN+10];
int B[MAXN+10];
struct SEG
{
int maxv[MAXN*4+10], minv[MAXN*4+10], lazy[MAXN*4+10];
void busy(int node, int tl, int tr)
{
maxv[node]+=lazy[node];
minv[node]+=lazy[node];
if(tl!=tr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
int querymin(int node, int tl, int tr)
{
busy(node, tl, tr);
if(tl==tr) return tl;
int mid=tl+tr>>1;
if(minv[node*2+1]+lazy[node*2+1]<=0) return querymin(node*2+1, mid+1, tr);
else return querymin(node*2, tl, mid);
}
int querymax(int node, int tl, int tr)
{
busy(node, tl, tr);
if(tl==tr) return tl;
int mid=tl+tr>>1;
if(maxv[node*2+1]+lazy[node*2+1]>=Vmax) return querymax(node*2+1, mid+1, tr);
else return querymax(node*2, tl, mid);
}
void update(int node, int tl, int tr, int l, int r, int k)
{
busy(node, tl, tr);
if(l<=tl && tr<=r)
{
lazy[node]+=k;
busy(node, tl, tr);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
minv[node]=min(minv[node*2], minv[node*2+1]);
maxv[node]=max(maxv[node*2], maxv[node*2+1]);
}
int querymin2(int node, int tl, int tr, int l, int r)
{
busy(node, tl, tr);
if(l<=tl && tr<=r) return minv[node];
if(r<tl || tr<l) return 987654321;
int mid=tl+tr>>1;
return min(querymin2(node*2, tl, mid, l, r), querymin2(node*2+1, mid+1, tr, l, r));
}
int querymax2(int node, int tl, int tr, int l, int r)
{
busy(node, tl, tr);
if(l<=tl && tr<=r) return maxv[node];
if(r<tl || tr<l) return -987654321;
int mid=tl+tr>>1;
return max(querymax2(node*2, tl, mid, l, r), querymax2(node*2+1, mid+1, tr, l, r));
}
}seg;
int main()
{
scanf("%d%d%d", &N, &Vmax, &V2); N--;
int t;
scanf(" %*c%d", &t);
for(int i=1; i<=N; i++)
{
int p; char q;
scanf(" %c%d", &q, &p);
if(q=='+') A[i]={p-t, i};
else A[i]={p-t, -i};
t=p;
}
sort(A+1, A+N+1);
int ans1=A[1].first-1, ans2=V2;
A[N+1].first=2147483647;
seg.update(1, 0, N+1, 0, N+1, V2);
for(int i=1; i<=N; i++)
{
printf("!%d\n", i);
if(A[i].second>0) B[A[i].second]=1, seg.update(1, 0, N+1, 0, A[i].second, -1);
else B[-A[i].second]=-1, seg.update(1, 0, N+1, 0, -A[i].second, 1);
if(A[i].first==A[i+1].first) continue;
int p=seg.querymin(1, 0, N+1);
int q=seg.querymax(1, 0, N+1);
if(p==0 && q==0)
{
ans1=A[i+1].first-1;
ans2=seg.querymax2(1, 0, N+1, 0, 0);
}
else if(p<q)
{
if(seg.querymax2(1, 0, N+1, 0, N+1)<=Vmax)
{
ans1=A[i+1].first-1;
if(q==0) ans2=seg.querymax2(1, 0, N+1, 0, 0);
else ans2=Vmax;
}
}
else
{
if(seg.querymin2(1, 0, N+1, 0, N+1)>=0)
{
ans1=A[i+1].first-1;
if(q==0) ans2=seg.querymax2(1, 0, N+1, 0, 0);
else ans2=Vmax;
}
}
}
if(ans1==2147483646) printf("infinity\n");
else printf("%d %d\n", ans1, ans2);
}
Compilation message
mp3player.cpp: In member function 'int SEG::querymin(int, int, int)':
mp3player.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int mid=tl+tr>>1;
| ~~^~~
mp3player.cpp: In member function 'int SEG::querymax(int, int, int)':
mp3player.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int mid=tl+tr>>1;
| ~~^~~
mp3player.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
mp3player.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int mid=tl+tr>>1;
| ~~^~~
mp3player.cpp: In member function 'int SEG::querymin2(int, int, int, int, int)':
mp3player.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int mid=tl+tr>>1;
| ~~^~~
mp3player.cpp: In member function 'int SEG::querymax2(int, int, int, int, int)':
mp3player.cpp:74:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
74 | int mid=tl+tr>>1;
| ~~^~~
mp3player.cpp: In function 'int main()':
mp3player.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
81 | scanf("%d%d%d", &N, &Vmax, &V2); N--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf(" %*c%d", &t);
| ~~~~~^~~~~~~~~~~~~~
mp3player.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
87 | scanf(" %c%d", &q, &p);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
1516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
1516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
1644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
5276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
