# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
237207 | DIvanCode | Deda (COCI17_deda) | C++14 | 854 ms | 8056 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |