# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
379159 |
2021-03-17T11:08:06 Z |
FatihSolak |
Deda (COCI17_deda) |
C++17 |
|
638 ms |
5228 KB |
#include <bits/stdc++.h>
#define N 200005
#define K 20
#define INF 1000000005
using namespace std;
int t[4*N];
void upd(int v,int l,int r,int pos,int val){
if(l == r){
t[v] = val;
return;
}
int m = (l+r)/2;
if(pos<=m){
upd(v*2,l,m,pos,val);
}
else{
upd(v*2+1,m+1,r,pos,val);
}
t[v] = min(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl)return INF;
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl+tr)/2;
return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
int get(int v,int tl,int tr,int l,int r,int val){
int tm = (tl+tr)/2;
if(tl == tr){
return (t[v] <=val?tl:-1);
}
if(get(v*2,tl,tm,l,r) <= val){
return get(v*2,tl,tm,l,r,val);
}
else{
return get(v*2+1,tm+1,tr,l,r,val);
}
}
void solve(){
int n,q;
cin >> n >> q;
for(int i=0;i<4*N;i++)t[i] = INF;
for(int i=0;i<q;i++){
char a;
int b,c;
cin >> a >> b >> c;
if(a == 'M'){
upd(1,1,n,c,b);
}
if(a == 'D'){
cout << get(1,1,n,c,n,b) << endl;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3436 KB |
Output is correct |
2 |
Correct |
3 ms |
3436 KB |
Output is correct |
3 |
Correct |
15 ms |
3436 KB |
Output is correct |
4 |
Correct |
638 ms |
5228 KB |
Output is correct |
5 |
Correct |
473 ms |
4272 KB |
Output is correct |
6 |
Correct |
581 ms |
4460 KB |
Output is correct |
7 |
Correct |
559 ms |
4588 KB |
Output is correct |