Submission #165790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
165790	2019-11-28T19:20:53 Z	muhi1112	Deda (COCI17_deda)	C++17	120 / 140	1000 ms	9248 KB

deda

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define f1 first
#define s2 second
#define pb push_back
#define mp make_pair
#define ll long long
#define fri(a) freopen(a,"r",stdin);
#define fro(a) freopen(a,"w",stdout);
const int N=2e5+5;

ll n,m,x,y,dizi[N];
pair<int,int>seg[4*N],k;
char c;

void update(int v,int tl,int tr,int pos,int val){
	if(tl==tr){
		seg[v]={val,tl};
	}
	else{
		int tm=(tl+tr)/2;
		if(pos<=tm){
			update(v*2,tl,tm,pos,val);
		}
		else{
			update(v*2+1,tm+1,tr,pos,val);
		}
		seg[v]=min(seg[v*2],seg[v*2+1]);
	}
}
pair<int,int> query(int v,int tl,int tr,int l,int r,int val){
	if(l<=tl && r>=tr){
		return (seg[v].f1)<=val?seg[v]:mp(INT_MAX,-1);
	}
	if(tr<l || tl>r){
		return {INT_MAX,-1};
	}
	int tm=(tl+tr)/2;
	pair<int,int> left=query(v*2,tl,tm,l,r,val);
	pair<int,int> right=query(v*2+1,tm+1,tr,l,r,val);
	if(left.f1<=val && right.f1<=val){
		return left;
	}
	return min(left,right);
}
int main(){
	//fri("in.txt");
	//fro("out.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	cin>>n>>m;
	for(int i=0;i<4*N;i++){
		seg[i]={INT_MAX,-1};
		if(i<N)dizi[i]=INT_MAX;
	}
	for(int i=0;i<m;i++){
		cin>>c>>x>>y;
		if(c=='M'){
			update(1,1,n,y,x);
			dizi[y]=x;
			// for(int j=0;j<2*n;j++){
			// 	cout<<seg[j].f1<<"----"<<seg[j].s2<<"  ";
			// }
			// cout<<endl;
		}
		else{
			k=query(1,1,n,y,n,x);
			if(k.s2==-1)cout<<k.s2<<endl;
			else{
				for(int i=k.s2;i>=y;i--){
					if(dizi[i]<=x){
						k.f1=dizi[i];
						k.s2=i;
					}
				}
				cout<<k.s2<<endl;
			}
		}
	}
return 0;
}

Subtask #1

120.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	8184 KB	Output is correct
2	Correct	7 ms	8184 KB	Output is correct
3	Correct	11 ms	8184 KB	Output is correct
4	Execution timed out	1075 ms	8876 KB	Time limit exceeded
5	Correct	263 ms	9080 KB	Output is correct
6	Correct	404 ms	9076 KB	Output is correct
7	Correct	789 ms	9248 KB	Output is correct