Submission #876605

# Submission time Handle Problem Language Result Execution time Memory
876605 2023-11-22T05:28:07 Z vjudge1 Deda (COCI17_deda) C++17
80 / 140
71 ms 4432 KB
#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();
	}
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 3 ms 1012 KB Output is correct
4 Incorrect 71 ms 4432 KB Output isn't correct
5 Correct 51 ms 3152 KB Output is correct
6 Incorrect 54 ms 3920 KB Output isn't correct
7 Incorrect 51 ms 2016 KB Output isn't correct