oj.uz

답안 #403325

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403325 2021-05-13T03:50:35 Z penguinhacker Deda (COCI17_deda) C++14
140 / 140
 119 ms 7872 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
int n, q, st[4*mxN];

void upd(int i, int x, int u=1, int l=0, int r=n-1) {
	if (l>i||r<i)
		return;
	if (l==r) {
		st[u]=x;
		return;
	}
	int mid=(l+r)/2;
	upd(i, x, 2*u, l, mid);
	upd(i, x, 2*u+1, mid+1, r);
	st[u]=min(st[2*u], st[2*u+1]);
}

int qry(int ql, int qr, int x, int u=1, int l=0, int r=n-1) {
	if (l>qr||r<ql||st[u]>x)
		return -1;
	if (l==r)
		return l+1;
	int mid=(l+r)/2;
	int al=qry(ql, qr, x, 2*u, l, mid);
	if (al^-1)
		return al;
	return qry(ql, qr, x, 2*u+1, mid+1, r);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	memset(st, 0x3f, 4*4*n);
	while(q--) {
		char t;
		int a, b;
		cin >> t >> a >> b;
		if (t=='M') {
			upd(b-1, a);
		} else {
			cout << qry(b-1, n-1, a) << "\n";
		}
	}
	return 0;
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 97 ms 7828 KB Output is correct
5 Correct 112 ms 6044 KB Output is correct
6 Correct 115 ms 7028 KB Output is correct
7 Correct 119 ms 7872 KB Output is correct