Submission #1139869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139869		imarn	RMQ (NOI17_rmq)	C++20	100 / 100	57 ms	14652 KiB

rmq

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=1e5+5;
vector<pii>g[mxn];
vector<pii>qr[mxn];
int a[mxn]{0};
int ans[mxn]{0};
bool vis[mxn]{0};
pii t[2*mxn];
multiset<int>ms;
pii query(int l,int r,int sz,pii rs={1e9,1e9}){
    for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
        if(l&1)rs=min(rs,t[l++]);
        if(r&1)rs=min(rs,t[--r]);
    }return rs;
}
void update(int i,int sz){
    i+=sz;t[i]={1e9,1e9};
    for(i>>=1;i;i>>=1)t[i]=min(t[2*i],t[2*i+1]);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=q;i++){
        int l,r,x;cin>>l>>r>>x;qr[x].pb({l,r});
        g[l].pb({0,x});g[r+1].pb({1,x});
    }
    for(int i=0;i<n;i++){
        for(auto [x,y]:g[i]){
            if(x==0)ms.insert(y);
            else ms.erase(ms.lower_bound(y));
        }if(!ms.empty())a[i]=*(--ms.end());
    }
    for(int i=0;i<n;i++)t[i+n]={a[i],i};
    for(int i=n-1;i>0;i--)t[i]=min(t[2*i],t[2*i+1]);
    bool ok=0;
    for(int i=0;i<n;i++){
        int mxl=-1,mnr=1e9;
        for(auto [l,r] : qr[i])mxl=max(mxl,l),mnr=min(mnr,r);
        if(mxl>mnr){ok=1;break;}
        if(mxl==-1)continue;
        pii rs=query(mxl,mnr+1,n);
        if(i<rs.f){ok=1;break;}
        ans[rs.s]=i;vis[i]=1;
        update(rs.s,n);
    }if(ok){for(int i=0;i<n;i++)cout<<-1<<' ';return 0;}
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        if(i<t[1].f){ok=1;break;}
        ans[t[1].s]=i;vis[i]=1;
        update(t[1].s,n);
    }if(ok){for(int i=0;i<n;i++)cout<<-1<<' ';return 0;}
    for(int i=0;i<n;i++)cout<<ans[i]<<' ';
}

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