oj.uz

Submission #237207

# Submission time Handle Problem Language Result Execution time Memory
237207 2020-06-05T09:06:08 Z DIvanCode Deda (COCI17_deda) C++14
140 / 140
 854 ms 8056 KB 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<queue>
#include<ctime>
#include<cassert>
#include<complex>
#include<string>
#include<cstring>
#include<chrono>
#include<random>
#include<bitset>
#include<iomanip>

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define sz(v) (int) v.size()

using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int INF = 2e9, MAX_N = 2e5 + 5;

int n, q, tree[MAX_N * 4];

void update(int v, int tl, int tr, int pos, int value) {
	if (tl + 1 == tr) {
		tree[v] = value;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos < tm) {
		update(v * 2 + 1, tl, tm, pos, value);
	} else {
		update(v * 2 + 2, tm, tr, pos, value);
	}
	tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]);
}

int get_min(int v, int tl, int tr, int L, int R) {
	if (tl >= R || L >= tr) {
		return INF;
	}
	if (L <= tl && tr <= R) {
		return tree[v];
	}
	int tm = (tl + tr) / 2;
	return min(get_min(v * 2 + 1, tl, tm, L, R), get_min(v * 2 + 2, tm, tr, L, R));
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	fill(tree, tree + n * 4, INF);
	while (q--) {
		char type;
		int a, b;
		cin >> type >> a >> b;
		if (type == 'M') {
			update(0, 1, n + 1, b, a);
		} else {
			if (get_min(0, 1, n + 1, b, n + 1) > a) {
				cout << "-1\n";
				continue;
			}
			int lef = b - 1, rig = n;
			while (lef + 1 < rig) {
				int mid = (lef + rig) / 2;
				if (get_min(0, 1, n + 1, b, mid + 1) <= a) {
					rig = mid;
				} else {
					lef = mid;
				}
			}
			cout << rig << "\n";
		}
	}
	return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 11 ms 512 KB Output is correct
4 Correct 854 ms 8056 KB Output is correct
5 Correct 609 ms 6156 KB Output is correct
6 Correct 744 ms 7160 KB Output is correct
7 Correct 820 ms 8056 KB Output is correct