# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
156684 | tpoppo | Deda (COCI17_deda) | C++14 | 120 ms | 7160 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define all(a) a.begin(),a.end()
#define endl '\n'
#define y1 y123132
#define sqr(a) ((a)*(a))
using namespace std;
const int N=200001;
const int md=1e9+7;
const int inf=1e9+3;
int n,q,sz;
int d[N*4];
void update(int v,int x)
{
v+=sz-1;
d[v]=x;
v/=2;
while(v)
{
d[v]=min(d[v+v],d[v+v+1]);
v/=2;
}
}
char c;
int x,y;
int get_first(int v, int lv, int rv, int l, int r, int x) {
if(lv > r || rv < l) return -1;
if(l <= lv && rv <= r) {
if(d[v] <= x) return -1;
while(lv != rv) {
int mid = lv + (rv-lv)/2;
if(d[2*v] <= x) {
v = 2*v+1;
lv = mid+1;
}else {
v = 2*v;
rv = mid;
}
}
return lv;
}
int mid = lv + (rv-lv)/2;
int rs = get_first(2*v, lv, mid, l, r, x);
if(rs != -1) return rs;
return get_first(2*v+1, mid+1, rv, l ,r, x);
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>q;
sz=1;
while(sz<n)sz*=2;
for(int i=1;i<=sz*2;++i)d[i]=inf;
for(int i=1;i<=q;++i)
{
cin>>c;
cin>>y>>x;
if(c=='M')update(x,y);
else
{
cout<<get_first(1,1,sz,x,n,y)<<endl;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |