oj.uz

Submission #1111181

# Submission time Handle Problem Language Result Execution time Memory
1111181 2024-11-11T16:07:05 Z nikolashami Deda (COCI17_deda) C++17
140 / 140
 623 ms 8008 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 412 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 623 ms 7832 KB Output is correct
5 Correct 357 ms 6472 KB Output is correct
6 Correct 433 ms 6880 KB Output is correct
7 Correct 552 ms 8008 KB Output is correct