Submission #1111181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111181		nikolashami	Deda (COCI17_deda)	C++17	140 / 140	623 ms	8008 KiB

deda

#include <bits/stdc++.h>
using namespace std;

int st[(int)8e5+4],n,q;

int qry(int l,int r,int node=1,int gl=1,int gr=n){
	if(gl>=l&&gr<=r)
		return st[node];
	int mid=(gl+gr)/2,res=1e9+1;
	if(gl<=r&&mid>=l)res=min(res,qry(l,r,node*2,gl,mid));
	if(mid+1<=r&&gr>=l)res=min(res,qry(l,r,node*2+1,mid+1,gr));
	return res;
}

void upd(int id,int val,int node=1,int gl=1,int gr=n){
	if(gl==gr){
		st[node]=val;
		return;
	}
	int mid=(gl+gr)/2;
	if(id<=mid)upd(id,val,node*2,gl,mid);
	else upd(id,val,node*2+1,mid+1,gr);
	st[node]=min(st[node*2+1],st[node*2]);
}

void ans(int lb,int ub){
	int l=lb,r=n,res=-1;
	while(l<=r){
		int m=(l+r)/2;
		if(qry(lb,m)<=ub){
			res=m;
			r=m-1;
		}else
			l=m+1;
	}
	cout<<res<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>q;

    fill(st,st+4*n+3,(int)1e9+2);

    while(q--){
    	char tp;
    	int x,y;
    	cin>>tp>>y>>x;
    	if(tp=='M')
    		upd(x,y);
    	else
    		ans(x,y);
    }
}

• Subtask 1: 140 / 140