oj.uz

Submission #871974

# Submission time Handle Problem Language Result Execution time Memory
871974 2023-11-12T05:23:10 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 154 ms 5624 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 7, SQ = 450;
int n, q, st[N], sq[SQ];

void add(int b, int x) {
	st[b] = x;
	sq[b / SQ] = min(sq[b / SQ], x);
}

int output(int b, int y) {
	for (int i = b; i < n; i++)
		if (i % SQ || i + SQ > n) {
			if (st[i] <= y)
				return i;
		}
		else {
			if (sq[i / SQ] <= y)
				for (int j = i; j < min(n, i + SQ); j++)
					if (st[j] <= y)
						return j;
			i += SQ - 1;
		}
	return -2;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);	
	cin >> n >> q;
	memset(sq, 63, sizeof sq);
	memset(st, 63, sizeof st);
	while (q--) {
		char c;
		int x, b;
		cin >> c >> x >> b;
		b--;
		if (c == 'M') 
			add(b, x);
		else 
			cout << output(b, x) + 1 << '\n';
	}
}

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 154 ms 5624 KB Output is correct
5 Correct 64 ms 5188 KB Output is correct
6 Correct 66 ms 5460 KB Output is correct
7 Correct 80 ms 5568 KB Output is correct