Submission #1139188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139188		12345678	RMQ (NOI17_rmq)	C++20	100 / 100	101 ms	9092 KiB

rmq

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int n, q, l, r, a, b[nx], cnt, used[nx], res[nx];
vector<pair<int, int>> d[nx];
pair<int, int> rng[nx];

struct segtree
{
    pair<int, int> mn[4*nx];
    int lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        mn[i].first+=lz[i];
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0; 
    }
    void build(int l, int r, int i)
    {
        if (l==r) return mn[i]={0, l}, void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        mn[i]=min(mn[2*i], mn[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        mn[i]=min(mn[2*i], mn[2*i+1]);
    }
    pair<int, int> query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return {1e9, 0};
        if (ql<=l&&r<=qr )return mn[i];
        int md=(l+r)/2;
        return min(query(l, md, 2*i, ql, qr), query(md+1, r ,2*i+1, ql, qr));
    }
} s;

pair<int, int> merge(pair<int, int> x, pair<int, int> y)
{
    if (x.first==-1||y.first==-1) return {-1, -1};
    if (max(x.first, y.first)<=min(x.second, y.second)) return {max(x.first, y.first), min(x.second, y.second)};
    return {-1, -1};
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    s.build(0, n-1, 1);
    for (int i=0; i<q; i++) cin>>l>>r>>a, d[a].push_back({l, r});
    for (int i=n-1; i>=0; i--)
    {
        rng[i]={0, n-1};
        for (auto x:d[i]) 
        {
            rng[i]=merge(rng[i], x);
            s.update(0, n-1, 1, x.first, x.second, 1);
        }
        if (rng[i].first==-1)
        {
            for (int j=0; j<n; j++) cout<<-1<<' ';
            cout<<'\n';
            return 0;
        }
    }
    for (int i=0; i<n; i++)
    {
        for (auto x:d[i]) s.update(0, n-1, 1, x.first, x.second, -1);
        auto tmp=s.query(0, n-1, 1, rng[i].first, rng[i].second);
        //cout<<"debug "<<i<<' '<<tmp.first<<' '<<tmp.second<<'\n';
        if (tmp.first)
        {
            for (int j=0; j<n; j++) cout<<-1<<' ';
            cout<<'\n';
            return 0;
        }
        res[tmp.second]=i;
        s.update(0, n-1, 1, tmp.second, tmp.second, 1e9);
    }
    for (int i=0; i<n; i++) cout<<res[i]<<' ';
}

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