Submission #1020546

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1020546	2024-07-12T06:51:55 Z	vjudge1	Deda (COCI17_deda)	C++11	140 / 140	90 ms	15044 KB

deda

#include <bits/stdc++.h>
using namespace std;
#define cl(x) (x << 1)
#define cr(x) (x << 1) + 1
long long seg[4*2* 100005];
long long test[4 *2* 100005];
long long search;
void pull(int index)
{
    if (seg[cl(index)] <= seg[cr(index)])
    {
        test[index] = test[cl(index)];
    }
    else
    {
        test[index] = test[cr(index)];
    }
    seg[index] = min(seg[cl(index)], seg[cr(index)]);
}
void build(int index, int l, int r)
{
    if (l == r)
    {
        seg[index] = LONG_LONG_MAX;
        test[index] = l;
        return;
    }
    int mid = (l + r) / 2;
    build(cl(index), l, mid);
    build(cr(index), mid + 1, r);
    pull(index);
}
void update(int index, int l, int r, long long v, int x)
{
    if (l == r)
    {
        seg[index] = min(seg[index], v);
        return;
    }
    int mid = (l + r) / 2;
    if (mid >= x)
    {
        update(cl(index), l, mid, v, x);
    }
    if (mid < x)
    {
        update(cr(index), mid + 1, r, v, x);
    }
    pull(index);
}
long long query(int index, int l, int r, int sl, int sr, long long target)
{
    if (sl > r || sr < l)
    {
        return -1;
    }
    // cout << " sl " << sl << " sr " << sr << " " << seg[index] << "\n";
    if (l <= sl && sr <= r)
    { //
        if (seg[index] > target)
        {
            return -1;
        }
        else
        {
            if (sl == sr)
            {
                if (seg[index] <= target)
                {
                    // cout<<" yes "<<sl<<" "<<seg[index]<<"\n";
                    return sl;
                }
                else
                {
                    return -1;
                }
            }
        }
    }
    long long ans = LONG_LONG_MAX;
    int mid = (sl + sr) / 2;
    long long temp = query(cl(index), l, r, sl, mid, target);
    if (l <= mid && temp != -1)
    {
        ans = min(ans, temp);
        return ans;
    }
    temp = query(cr(index), l, r, mid + 1, sr, target);
    if (r > mid && temp != -1)
    {
        ans = min(ans, temp);
    }
    if (ans == LONG_LONG_MAX)
    {
        return -1;
    }
    return ans;
}
void new_query(int index, int l, int r)
{
    if (l == r)
    {
        cout << seg[index] << " ";
        return;
    }
    int mid = (l + r) / 2;
    new_query(cl(index), l, mid);
    new_query(cr(index), mid + 1, r);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    build(1, 1, n);
    for (int i = 0; i < q; i++)
    {
        char way;
        int a, b;
        cin >> way >> a >> b;
        if (way == 'M')
        {
            update(1, 1, n, a, b);
            // new_query(1, 1, n);
            // cout << "\n";
        }
        else
        { // greater or equal to a    less than or equal to y
            long long temp = query(1, b, n, 1, n, a);
            cout << temp << "\n";
        }
    }
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	2 ms	2544 KB	Output is correct
4	Correct	87 ms	15044 KB	Output is correct
5	Correct	76 ms	7424 KB	Output is correct
6	Correct	84 ms	14964 KB	Output is correct
7	Correct	90 ms	14928 KB	Output is correct