Submission #446989

#	Time	Username	Problem	Language	Result	Execution time	Memory
446989		Kheem	Deda (COCI17_deda)	C++14	60 / 140	5 ms	3148 KiB

deda

// COCI DEDA

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ve vector 
#define endl "\n"
typedef pair<int ,int> ii;
#define sz(a) (int)(a).size()
#define ALL(t) (t).begin(),(t).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

int inf = INT_MAX;
const int mxn=2e5+5;
int a[mxn], st[mxn];
int n,q;
char ch;
void build(int p, int L, int R){
	if(L==R){
		a[L]=inf;
		st[p]=L;
	}else {
		int mid = (L+R)/2;
		build(2*p, L, mid);
		build(2*p+1, mid+1, R);
		int p1 = st[2*p], p2 = st[2*p+1];
		st[p] = (a[p1] <= a[p2]) ? p1 : p2;
	}
}
void update(int p, int L, int R, int idx, int val){
	if(L==R){
		a[L]=val;
	}else{
		int mid = (L+R)/2;
		if(idx<=mid)update(2*p, L, mid, idx, val);
		else update(2*p+1, mid+1, R, idx, val);
		int p1 = st[2*p], p2 = st[2*p+1];
		st[p] = (a[p1] <= a[p2]) ? p1 : p2;
	}
}
int query(int p, int L, int R, int i, int j,int val){
	if(i>j)return -1;
	else if(i==L && R==j){
		if(a[st[p]] > val)return -1;
		while(L!=R){
			int mid  = (L+R)/2;
			if(a[st[2*p]] <= val){
				R=mid;
				p=2*p;
			}else{
				L=mid+1;
				p=2*p+1;
			}
		}	
		return L;
	}
	else{
		int mid = (L+R)/2;
		int p1 = query(2*p, L, mid, i, min(mid,j), val);
		// int p2 = query(2*p+1, mid+1, R, max(mid+1, i), j, val);
		if(p1==-1)return query(2*p+1, mid+1, R, max(mid+1, i), j, val);
		return p1;
	}
}

int main(){
	FAST
	cin>>n>>q;
	build(1,1,n);
	while(q--){
		cin>>ch;
		if(ch=='M'){
			int X,A;
			cin>>X>>A;
			update(1,1,n,A,X);
		}else{
			int Y,B;
			cin>>Y>>B;
			int ans = query(1,1,n,B,n,Y);
			cout<<ans<<endl;			
		}
	}
}

• Subtask 1: 60 / 140