Submission #1095086

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1095086	2024-10-01T08:46:53 Z	kerem	Deda (COCI17_deda)	C++14	140 / 140	99 ms	7728 KB

deda

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define MIN INT_MIN
#define MAX INT_MAX
#define LLMAX LLONG_MAX
#define LLMIN LLONG_MIN
#define N 200000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed<<setprecision(9)
typedef pair<int,int> pii;

int n,q;
vector<int> st(2*N+5, MAX);

int f(int x,int d){
	if(x>=n) return x-n+1;
	if(st[x<<1]<=d) return f(x<<1,d);
	else return f(x<<1|1,d);
}
void update(int x,int val){
	x+=n-1;
	st[x]=val;
	x>>=1;
	while(x){
		st[x]=min(st[x<<1],st[x<<1|1]);
		x>>=1;
	}
}
int query(int ll,int d){
	int l=ll+n-1,r=2*n;
	int sl=1,sr=2*n;
	vector<pii> v;
	while(l<r){
		if(l&1) v.pb({sl++,l++});
		if(r&1) v.pb({--sr,--r});
		l>>=1;
		r>>=1;
	}
	sort(all(v));
	int x=0;
	for(auto i:v) if(st[i.sc]<=d){
		x=i.sc;
		break;
	}
	if(!x) return -1;
	return f(x,d);
}
void solve(){
	cin >> n >> q;
	while(q--){
		char c;
		cin >> c;
		if(c=='M'){
			int x,y;
			cin >> y >> x;
			update(x,y);
		}
		if(c=='D'){
			int x,y;
			cin >> y >> x;
			cout << query(x,y) << endl;
		}
	}
}
int32_t main(){
	fast;
	int test=1;
	//~ cin >> test;
	while(test--){
		solve();
	}
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3416 KB	Output is correct
2	Correct	2 ms	3420 KB	Output is correct
3	Correct	3 ms	3420 KB	Output is correct
4	Correct	97 ms	7728 KB	Output is correct
5	Correct	79 ms	6936 KB	Output is correct
6	Correct	99 ms	7420 KB	Output is correct
7	Correct	92 ms	7444 KB	Output is correct