Submission #403325

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403325	2021-05-13T03:50:35 Z	penguinhacker	Deda (COCI17_deda)	C++14	140 / 140	119 ms	7872 KB

deda

#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

#	Verdict	Execution time	Memory	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