Submission #243606

#	Time	Username	Problem	Language	Result	Execution time	Memory
243606		SamAnd	RMQ (NOI17_rmq)	C++17	100 / 100	109 ms	10936 KiB

rmq

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 100005;

int n, q;
pair<int, int> u[N];

int t[N * 4];

void ubd(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        t[pos] = max(t[pos], y);
        return;
    }
    int m = (tl + tr) / 2;
    ubd(tl, m, l, min(m, r), y, pos * 2);
    ubd(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
}

int qry(int tl, int tr, int x, int pos)
{
    if (tl == tr)
        return t[pos];
    int m = (tl + tr) / 2;
    if (x <= m)
        return max(qry(tl, m, x, pos * 2), t[pos]);
    return max(qry(m + 1, tr, x, pos * 2 + 1), t[pos]);
}

pair<int, int> hat(const pair<int, int>& a, const pair<int, int>& b)
{
    return m_p(max(a.fi, b.fi), min(a.se, b.se));
}

vector<int> v[N];

int ans[N];

void solv()
{
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; ++i)
        u[i] = m_p(0, n - 1);
    for (int i = 0; i < q; ++i)
    {
        int l, r, y;
        scanf("%d%d%d", &l, &r, &y);
        ubd(0, n - 1, l, r, y, 1);
        u[y] = hat(u[y], m_p(l, r));
    }
    for (int i = 0; i < n; ++i)
    {
        if (u[i].fi > u[i].se)
        {
            for (int i = 0; i < n; ++i)
                printf("-1 ");
            printf("\n");
            return;
        }
        v[u[i].fi].push_back((i + 1));
        v[u[i].se + 1].push_back(-(i + 1));
    }
    set<int> s;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < v[i].size(); ++j)
        {
            if (v[i][j] > 0)
                s.insert(v[i][j] - 1);
            else
            {
                if (s.find(-v[i][j] - 1) != s.end())
                {
                    for (int i = 0; i < n; ++i)
                        printf("-1 ");
                    printf("\n");
                    return;
                }
            }
        }
        auto it = s.lower_bound(qry(0, n - 1, i, 1));
        if (it == s.end())
        {
            for (int i = 0; i < n; ++i)
                printf("-1 ");
            printf("\n");
            return;
        }
        ans[i] = *it;
        s.erase(it);
    }
    for (int i = 0; i < n; ++i)
        printf("%d ", ans[i]);
    printf("\n");
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

rmq.cpp: In function 'void solv()':
rmq.cpp:78:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
rmq.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~
rmq.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &l, &r, &y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33