제출 #68307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68307		hoangmaihuy	Deda (COCI17_deda)	C++14	140 / 140	669 ms	17268 KiB

deda

#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 / 140