Submission #876609

#	Time	Username	Problem	Language	Result	Execution time	Memory
876609		vjudge1	Deda (COCI17_deda)	C++17	140 / 140	96 ms	8272 KiB

deda

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 10;
const int maxn = 1e6;
const ll mod = 998244353;
const int sq = 400;

int mn[N], a[N];
bool mark[N];
int n, q;

void upd(){
	int x, y;	cin>> x>> y;
	y--;
	a[y] = x;
	mn[y / sq] = min(mn[y / sq], x);
	mark[y] = 1;
}

void check(){
	int x, y;	cin>> x>> y;
	y--;
	for(int i = y; i < min(y / sq * sq + sq, n); i++){
		if(mark[i] && a[i] <= x){
			cout<< i + 1 <<"\n";
			
			return;
		}
	}
	for(int i = y / sq + 1; i <= (n - 1) / sq; i++){
		if(mn[i] <= x){
			for(int j = sq * i; j < min(n, sq * i + sq); j++){
				if(mark[j] && a[j] <= x){
					cout<< j + 1<<"\n";
					return;
				}
			}
		}
	}
	cout<< -1 <<"\n";
}

void read_query(){
	for(int i = 0; i < q; i++){
		char ch;	cin>> ch;
		if(ch == 'M'){
			upd();
		}
		else{
			check();
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
	cin>> n>> q;
	for(int i = 0; i < N; i++)
		mn[i] = 1e9 + 10;
	read_query();
	return 0;
}

• Subtask 1: 140 / 140