Submission #876605

#	Time	Username	Problem	Language	Result	Execution time	Memory
876605		vjudge1	Deda (COCI17_deda)	C++17	80 / 140	71 ms	4432 KiB

deda

#include <bits/stdc++.h>

using namespace std;

#define fast_io ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define file_io freopen(".in","r",stdin);freopen(".out","w",stdout);
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const long long INF = 1e18;
const int M = 1e9 + 7, N = 2e5 + 10, maxn = 1e5 + 5, sq = 500;

int n, q;
int a[N], ans[sq];

void ins(){
	int ps, x;
	cin >> ps >> x;
	a[x] = ps;
	ans[x/sq] = min(ans[x/sq], ps);
}

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

int main(){
	fast_io;
	cin >> n >> q;
	for(int i = 0; i < maxn; i++)
		a[i] = 1e9 + 1;
	for(int i = 0; i < sq; i++)
		ans[i] = 1e9 + 1;
	while(q--){
		char tp;
		cin >> tp;
		if(tp == 'M')
			ins();
		else
			solve();
	}
}

• Subtask 1: 80 / 140