# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
866819 | RaulAndrei01 | Deda (COCI17_deda) | C++17 | 378 ms | 7252 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 <vector>
#include <iostream>
using namespace std;
const int NMAX = 2e5;
const int INF = 1e9 + 10;
struct AINT {
vector<int> aint;
int n , offset;
AINT (int _n)
{
n = _n;
offset = 1;
while (offset < n) offset <<= 1;
aint.resize(2 * offset , INF);
}
void update (int pos , int val)
{
_update (1 , 1 , offset , pos , val);
}
void _update (int nod , int l , int r , int pos , int val)
{
if (l == r)
{
if (l == pos) aint[nod] = val;
return;
}
if (pos < l || r < pos) return;
int mid = (l + r) / 2;
_update(2 * nod , l , mid, pos, val);
_update(2*nod+1, mid+1, r, pos, val);
aint[nod] = merge (aint[2*nod] , aint[2*nod+1]);
}
int merge (int nod1, int nod2)
{
return min(nod1, nod2);
}
int bs (int pos , int val)
{
int nod = offset + pos - 1;
while (aint[nod] > val && nod > 0)
{
if (nod == 1) nod = 0;
else if (nod%2 == 1 && (nod & (nod+1)) == 0) {
nod = 0;
}
else if (nod % 2 == 1) nod = nod / 2 + 1;
else nod /= 2;
}
// cout << nod << '\n';
if (nod == 0) return -1;
while (nod < offset)
{
if (aint[2*nod] > val) nod = 2 * nod + 1;
else nod = 2 * nod;
}
return nod - offset + 1;
}
};
int main ()
{
int n , q; cin >> n >> q;
AINT aint(n);
while (q--)
{
char c; cin >> c;
if (c == 'M')
{
int x, a; cin >> x >> a;
aint.update(a, x);
}
else {
int y, b; cin >> y >> b;
cout << aint.bs(b, y) << '\n';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |