oj.uz

Submission #237213

# Submission time Handle Problem Language Result Execution time Memory
237213 2020-06-05T09:20:58 Z Mlxa Deda (COCI17_deda) C++14
140 / 140
 402 ms 5740 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N   = 1 << 18;
const int INF = 1e18;

int n;
int q;
int t[2 * N];

void upd(int i, int v) {
	t[i += N] = v;
	for (i /= 2; i > 0; i /= 2) {
		t[i] = min(t[i + i], t[i + i + 1]);
	}
}

int query(int l, int r) {
	int mn = INF;
	for (l += N, r += N; l <= r; l /= 2, r /= 2) {
		if (l % 2 == 1) {
			mn = min(mn, t[l++]);
		}
		if (r % 2 == 0) {
			mn = min(mn, t[r--]);
		}
	}
	return mn;
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	fill_n(t, 2 * N, INF);

	cin >> n >> q;
	while (q--) {
		char tp;
		cin >> tp;
		if (tp == 'M') {
			int x;
			int y;
			cin >> y >> x;
			upd(x, y);
		} else {
			int x;
			int y;
			cin >> y >> x;
			if (query(x, n) > y) {
				cout << "-1\n";
				continue;
			}
			int lef = x - 1, rig = n;
			while (rig - lef > 1) {
				int mid = (lef + rig) / 2;
				if (query(x, mid) <= y) {
					rig = mid;
				} else {
					lef = mid;
				}
			}
			cout << rig << "\n";
		}
	}

	return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 7 ms 4480 KB Output is correct
3 Correct 10 ms 4480 KB Output is correct
4 Correct 402 ms 5740 KB Output is correct
5 Correct 272 ms 5368 KB Output is correct
6 Correct 321 ms 5564 KB Output is correct
7 Correct 356 ms 5624 KB Output is correct