oj.uz

Submission #876612

# Submission time Handle Problem Language Result Execution time Memory
876612 2023-11-22T05:32:35 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 106 ms 2180 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 = 2e5 + 5, sq = 600;

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

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

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

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

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 106 ms 2176 KB Output is correct
5 Correct 54 ms 1872 KB Output is correct
6 Correct 62 ms 2128 KB Output is correct
7 Correct 67 ms 2180 KB Output is correct