# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
975740 |
2024-05-05T19:50:47 Z |
vjudge1 |
Deda (COCI17_deda) |
C++17 |
|
742 ms |
11028 KB |
#include <bits/stdc++.h>
#define MAXN 200005
#define MOD 998244353
using namespace std;
typedef long long ll;
ll st[4*MAXN], ar[MAXN],n,k,a,b,c,d;
void build(int pos, int l, int r){
//cout << "aqui2\n";
if(l == r){
st[pos] = 1e17;
return;
}
int m = (l+r)/2;
build(pos*2, l,m);
build(pos*2 +1, m+1,r);
st[pos] = min(st[pos*2], st[pos*2 + 1]);
return;
}
void update(int pos, int indice, int valor, int l, int r){
//cout << "aqui\n";
if(l == r){
st[pos] = valor;
return;
}
int m = (l+r)/2;
if(indice <= m)update(pos*2, indice, valor, l,m);
else update(pos*2 + 1, indice, valor, m+1,r);
st[pos] = min(st[pos*2], st[pos*2 + 1]);
return;
}
ll query(int pos, int l, int r, int lq, int rq){
if(l >= lq && r <= rq){
return st[pos];
}
if(l > rq || r < lq){
return 1e17;
}
int m = (l+r)/2;
return min(query(pos*2, l,m,lq,rq), query(pos*2 + 1, m+1,r,lq,rq));
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
build(1,1,n);
char op;
for(int i =0; i < k; i++){
cin >> op;
if(op == 'M'){
cin >> b >> c;
//cout << "entra\n";
update(1,c,b,1,n);
}else{
//cout << "query " << '\n';
cin >> a >> b;
int ini = b, fin = n;
int res = -1;
while(ini <= fin){
int mitad = (ini + fin)/2;
if(query(1,1,n,ini,mitad) <= a){
fin = mitad - 1;
res = mitad;
}else ini = mitad + 1;
}
cout << res << '\n';
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
7 ms |
2396 KB |
Output is correct |
4 |
Correct |
742 ms |
11028 KB |
Output is correct |
5 |
Correct |
470 ms |
8592 KB |
Output is correct |
6 |
Correct |
559 ms |
11020 KB |
Output is correct |
7 |
Correct |
661 ms |
11012 KB |
Output is correct |