제출 #871974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871974		vjudge1	Deda (COCI17_deda)	C++17	140 / 140	154 ms	5624 KiB

deda

#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 / 140