oj.uz

Submission #876609

# Submission time Handle Problem Language Result Execution time Memory
876609 2023-11-22T05:30:02 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 96 ms 8272 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 1 ms 6872 KB Output is correct
3 Correct 3 ms 7004 KB Output is correct
4 Correct 96 ms 8272 KB Output is correct
5 Correct 85 ms 7760 KB Output is correct
6 Correct 91 ms 7940 KB Output is correct
7 Correct 87 ms 8060 KB Output is correct