Submission #1074378

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1074378	2024-08-25T10:10:44 Z	rayan_bd	Deda (COCI17_deda)	C++17	140 / 140	442 ms	13136 KB

deda

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 


#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())

const int mxN = 2e5 + 500;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ld EPS = 1e-9;

pair<ll,ll> seg[mxN*4];

void build(ll node,ll start,ll end){
	if(start==end){
		seg[node]={INF,start};
		return;
	}
	ll mid=start+(end-start)/2;
	build(node*2+1,start,mid);
	build(node*2+2,mid+1,end);
	seg[node]=min(seg[node*2+1],seg[node*2+2]);
}

void upd(ll node,ll start,ll end,ll point,ll v){
	if(start==end){
		seg[node].first=v;
		return;
	}
	ll mid=start+(end-start)/2;
	if(point<=mid) upd(node*2+1,start,mid,point,v);
	else upd(node*2+2,mid+1,end,point,v);
	seg[node]=min(seg[node*2+1],seg[node*2+2]);
}

pair<ll,ll> qry(ll node,ll start,ll end,ll l,ll r,ll y){
	if (start>r||end<l){
		return {INF,INF};
	}
	if(start>=l&&end<=r) return seg[node];
	ll mid=start+(end-start)/2;
	auto lft=qry(node*2+1,start,mid,l,r,y);
	if(lft.first<=y){
		return lft;
	}
	return qry(node*2+2,mid+1,end,l,r,y);
}

void solve(ll tc) {
    ll n,q,station,child;cin>>n>>q;
    char ch;
    build(0,1,n);
    while(q--){
    	cin>>ch>>station>>child;
    	if(ch=='M'){
    		upd(0,1,n,child,station);
    	}else{
    		ll st=child,en=n,ans=-1;
    		while(st<=en){
    			ll mid=st+(en-st)/2;
    			auto v=qry(0,1,n,st,mid,station);
    			if(v.first<=station){
    				ans=v.second;
    				en=mid-1;
    			}else{
    				st=mid+1;
    			}
    		}
    		show(ans);
    	}
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve(0);
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	464 KB	Output is correct
3	Correct	4 ms	348 KB	Output is correct
4	Correct	442 ms	13136 KB	Output is correct
5	Correct	236 ms	8560 KB	Output is correct
6	Correct	292 ms	12884 KB	Output is correct
7	Correct	305 ms	12884 KB	Output is correct