#include <bits/stdc++.h>
#define int long long
using namespace std;
int const mxN = 2e5+5;
int n,q, seg[8*mxN], a[8*mxN];
int get ( int node, int l_n, int r_n, int l, int r, int v) {
if(seg[node]>v) return 1e17;
if(l_n==r_n-1) return l_n;
int m = (l_n+r_n)/2;
if(seg[node*2+1]<=v && m>l && l_n<r) return get(node*2+1, l_n, m, l, r, v );
else if(seg[node*2+2]<=v && (r>m && l<r_n)) return get(node*2+2, m, r_n, l, r, v );
else return 1e17;
}
void update(int node, int l, int r, int x, int v ) {
if(l==r-1) { seg[node] = v; return; }
int m = (l+r)/2;
if(x<m) update(node*2+1, l, m, x, v);
else update(node*2+2, m, r, x, v);
seg[node] = min(seg[node*2+1], seg[node*2+2]);
}
int dist[mxN];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>q;
int pw = (1<<(__lg(n)+1));
for(int i=0; i<8*mxN; i++) seg[i] = 1e17;
for(int i=0; i<=n; i++) dist[i] = 1e17;
for(int i=0; i<q; i++) {
char c; cin>>c;
if(c=='M') {
int x,a; cin>>x>>a;
update(0,0,pw,a,x);
dist[a] = x;
}
else {
int rides,b; cin>>rides>>b;
int ans = get(0,0,pw,b,n+1, rides);
cout<<(ans==1e17? -1:ans)<<'\n';
bool f = 1;
//for(int j=b; j<=n; j++) if(dist[j]<=rides) { cout<<j<<'\n'; f = 0; break;}
// if(f) cout<<"-1\n";
}
}
return 0;
}
Compilation message
deda.cpp: In function 'int main()':
deda.cpp:47:12: warning: unused variable 'f' [-Wunused-variable]
47 | bool f = 1;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
14424 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14428 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
14428 KB |
Output isn't correct |
| 4 |
Incorrect |
53 ms |
17612 KB |
Output isn't correct |
| 5 |
Incorrect |
63 ms |
17236 KB |
Output isn't correct |
| 6 |
Incorrect |
70 ms |
17400 KB |
Output isn't correct |
| 7 |
Incorrect |
69 ms |
17460 KB |
Output isn't correct |
