///Never gonna give you up.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long long int lli;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
const ll mod=(ll)1e9+7;
const ll mod1=998244353;
///the defines :)
#define endl '\n'
#define vi vector<int>
#define vll vector<ll>
#define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i];
#define all(arr) arr.begin(),arr.end()
#define allr(arr) arr.rbegin(),arr.rend()
#define sz size()
#define int long long
struct segtree
{
int siz;
vector<int>vals;
int neutram_element=0;
void init(int n)
{
siz=1;
while(siz<n)siz*=2;
vals.resize(siz*2);
}
int merg(int a,int b)
{
return min(a,b);
}
int single(int a)
{
return a;
}
void Set(int i,int val,int x,int lx,int rx)
{
// cout<<lx<<" "<<rx<<" "<<x<<endl;
if(lx==rx)
{
vals[x]=single(val);
return;
}
int mid=(lx+rx+1)/2;
if(i<mid)
Set(i,val,2*x+1,lx,mid-1);
else Set(i,val,2*x+2,mid,rx);
vals[x]=merg(vals[2*x+1],vals[2*x+2]);
}
void Set(int i,int v)
{
Set(i,v,0,0,siz-1);
}
int calc(int l,int r,int v,int x,int lx,int rx)
{
if(lx>r||rx<l||vals[x]>v)return 1e9+2;
if(lx==rx)return lx;
int mid=(lx+rx+1)/2;
// cout<<lx<<" "<<rx<<" "<<x<<" "<<mid<<endl;
int e=calc(l,r,v,2*x+1,lx,mid-1);
if(e==1e9+2)
e=calc(l,r,v,2*x+2,mid,rx);
return e;
}
int calc(int l,int r,int v)
{
return calc(l,r,v,0,0,siz-1);
}
};
void preprocess() {}
void solve()
{
int n,q;
cin>>n>>q;
segtree st;
st.init(n);
for(int i=0;i<n;i++)
st.Set(i,1e9+2);
while(q--)
{
char x;
cin>>x;
if(x=='M')
{
int a,b;
cin>>a>>b;
b--;
st.Set(b,a);
}
else
{
int a,b;
cin>>a>>b;
b--;
int haha=st.calc(b,n-1,a);
if(haha==1e9+2)cout<<-1<<endl;
else cout<<haha+1<<endl;
}
}
}
signed main()
{
// freopen("div7.in","r",stdin);
//freopen("div7.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
preprocess();
//bla();
int t=1;
// cin>>t;
while(t--)
solve();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
77 ms |
9032 KB |
Output is correct |
| 5 |
Correct |
75 ms |
6504 KB |
Output is correct |
| 6 |
Correct |
81 ms |
8788 KB |
Output is correct |
| 7 |
Correct |
87 ms |
8788 KB |
Output is correct |
