oj.uz

Submission #68307

# Submission time Handle Problem Language Result Execution time Memory
68307 2018-08-16T14:13:08 Z hoangmaihuy Deda (COCI17_deda) C++14
140 / 140
 669 ms 17268 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+1;
const int INF = 1e9+1;

int n, q;
int t[4*N];

void update(int i, int lo, int hi, int u, int val)
{
    if (lo == hi)
    {
        if (!t[i] || t[i] > val) t[i] = val;
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) update(i*2, lo, mid, u, val);
    else update(i*2+1, mid+1, hi, u, val);
    if (t[i*2] && t[i*2+1]) t[i] = min(t[i*2], t[i*2+1]);
    else if (!t[i*2]) t[i] = t[i*2+1];
    else t[i] = t[i*2];
}

int findPos(int i, int lo, int hi, int start, int bound)
{
    if (lo == hi)
    {
        if (t[i] && t[i] <= bound) return lo;
        return -1;
    }
    int mid = (lo + hi) >> 1;
    if (mid < start) return findPos(i*2+1, mid+1, hi, start, bound);
    if (lo >= start)
    {
        int left = t[i*2], right = t[i*2+1];
        if (!left) left = INF;
        if (!right) right = INF;
        if (left <= bound) return findPos(i*2, lo, mid, start, bound);
        if (right <= bound) return findPos(i*2+1, mid+1, hi, start, bound);
        return -1;
    }
    else
    {
        int tmp = findPos(i*2, lo, mid, start, bound);
        if (tmp != -1) return tmp;
        return findPos(i*2+1, mid+1, hi, start, bound);
    }
}

int main()
{
    //ifstream cin("in.txt");
    cin >> n >> q;
    while (q--)
    {
        char kind;
        cin >> kind;
        if (kind == 'M')
        {
            int id, val;
            cin >> val >> id;
            update(1, 1, n, id, val);
        }
        else
        {
            int start, bound;
            cin >> bound >> start;
            cout << findPos(1, 1, n, start, bound) << "\n";
        }
    }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 380 KB Output is correct
3 Correct 17 ms 416 KB Output is correct
4 Correct 669 ms 6728 KB Output is correct
5 Correct 573 ms 9328 KB Output is correct
6 Correct 579 ms 13784 KB Output is correct
7 Correct 580 ms 17268 KB Output is correct