oj.uz

Submission #1095069

# Submission time Handle Problem Language Result Execution time Memory
1095069 2024-10-01T08:18:55 Z vjudge1 Deda (COCI17_deda) C++17
20 / 140
 89 ms 7724 KB 
#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;
	vector<int> v;
	while(l<r){
		if(l&1) v.pb(l++);
		if(r&1) v.pb(--r);
		l>>=1;
		r>>=1;
	}
	int x=0;
	for(auto i:v) if(st[i]<=d){
		x=i;
		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
20.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Incorrect 2 ms 3420 KB Output isn't correct
3 Incorrect 3 ms 3420 KB Output isn't correct
4 Incorrect 89 ms 7724 KB Output isn't correct
5 Incorrect 69 ms 7112 KB Output isn't correct
6 Incorrect 80 ms 7356 KB Output isn't correct
7 Incorrect 89 ms 7508 KB Output isn't correct