# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
472971 | _L__ | Deda (COCI17_deda) | C++17 | 1096 ms | 4172 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.
// This code is written by _L__
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>;
#define endl '\n'
#define F_word ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
typedef long long ll;
typedef long double ld;
const ll mod = 1e9+7, N = 2e5+13, inf = 1e9+1;
const ld E = 1e-6;
#define ff first
#define ss second
int t[4*N];
void build(int v, int tl, int tr){
if(tl>tr)return;
if(tl == tr){t[v] = inf; return;}
int tm = (tl+tr)/2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
t[v] = min(t[v*2], t[v*2+1]);
}
void update(int v, int tl, int tr, int idx, int rx){
if(tl > tr) return;
if(tl == tr){t[v] = rx; return;}
int tm = (tl+tr)/2;
if(idx > tm) update(v*2+1, tm+1, tr, idx, rx);
else update(v*2, tl, tm, idx, rx);
t[v] = min(t[v*2], t[v*2+1]);
}
int query(int v, int tl, int tr, int l, int r){
if(tl > tr) return inf;
if(l > tr || r < tl) return inf;
if(tl == l && tr == r) return t[v];
int tm = (tl+tr)/2;
return min(query(v*2, tl, tm, l, min(tm, r)), query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
int lower(int l, int r, int y){
int n = r;
int ans = -1;
while(l<=r){
int mid = (l+r)/2;
int x = query(1,1,n,l,mid);
if(x <= y){
ans = mid;
r = mid-1;
} else l = mid+1;
}
return ans;
}
int main(void){
F_word;
int n, q; cin >> n >> q;
build(1, 1, n);
int a[n] = {};
while(q--){
char c; cin >> c;
if(c == 'M'){
int x; int i; cin >> x >> i;
a[i] = x;
update(1,1,n,i,x);
} else {
int b, y; cin >> y >> b;
int x = lower(b,n,y);
cout << x << endl;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |