#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define MIN INT_MIN
#define MAX INT_MAX
#define LLMAX LLONG_MAX
#define LLMIN LLONG_MIN
#define N 200000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed<<setprecision(9)
typedef pair<int,int> pii;
int n,q;
vector<int> st(2*N+5, MAX);
int f(int x,int d){
if(x>=n) return x-n+1;
if(st[x<<1]<=d) return f(x<<1,d);
else return f(x<<1|1,d);
}
void update(int x,int val){
x+=n-1;
st[x]=val;
x>>=1;
while(x){
st[x]=min(st[x<<1],st[x<<1|1]);
x>>=1;
}
}
int query(int ll,int d){
int l=ll+n-1,r=2*n;
vector<int> v;
while(l<=r){
if(l&1) v.pb(l++);
if(r&1) v.pb(--r);
l>>=1;
r>>=1;
}
int x=0;
for(auto i:v) if(st[i]<=d){
x=i;
break;
}
if(!x) return -1;
return f(x,d);
}
void solve(){
cin >> n >> q;
while(q--){
char c;
cin >> c;
if(c=='M'){
int x,y;
cin >> y >> x;
update(x,y);
}
if(c=='D'){
int x,y;
cin >> y >> x;
cout << query(x,y) << endl;
}
}
}
int32_t main(){
fast;
int test=1;
//~ cin >> test;
while(test--){
solve();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
3420 KB |
Output isn't correct |
| 4 |
Incorrect |
90 ms |
8128 KB |
Output isn't correct |
| 5 |
Incorrect |
72 ms |
7508 KB |
Output isn't correct |
| 6 |
Incorrect |
80 ms |
7764 KB |
Output isn't correct |
| 7 |
Incorrect |
85 ms |
8016 KB |
Output isn't correct |
