Submission #847789

#	Time	Username	Problem	Language	Result	Execution time	Memory
847789		HoriaHaivas	RMQ (NOI17_rmq)	C++14	100 / 100	67 ms	11208 KiB

rmq

/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

struct qq
{
    int l;
    int r;
    int x;
};

struct ptval
{
    int nr;
    int poz;
};

ptval val[100001];
const int inf=INT_MAX;
qq query[100001];
qq query2[100001];
qq aux[100001];
qq aux2[100001];
int st[100001];
int finl[100001];
bool placed[100001];
bool used[100001];
int lazy[400001];
int aint[400001];

bool cmp (qq a, qq b)
{
    if (a.x!=b.x)
        return a.x<b.x;
    else if (a.l!=b.l)
        return a.l<b.l;
    else
        return a.r<b.r;
}

bool cmp2(ptval a, ptval b)
{
    if (a.nr!=b.nr)
        return a.nr>b.nr;
    else
        return a.poz<b.poz;
}

bool cmp3 (qq a, qq b)
{
    if (a.l!=b.l)
        return a.l<b.l;
    else if (a.r!=b.r)
        return a.r<b.r;
    else
        return a.x<b.x;
}

void propagate(int parent, int child)
{
    lazy[child]=lazy[parent];
}

void lazy_update (int l, int r, int val, int qa, int qb, int x)
{
    if (lazy[val]!=-1)
    {
        if (r!=l)
        {
            propagate(val,val*2);
            propagate(val,val*2+1);
        }
        lazy[val]=-1;
    }
    if (l>qb || r<qa)
        return;
    if (qa<=l && r<=qb)
    {
        lazy[val]=x;
        return;
    }
    int mid;
    mid=(l+r)/2;
    if (qa<=mid)
        lazy_update(l,mid,val*2,qa,qb,x);
    if (qb>mid)
        lazy_update(mid+1,r,val*2+1,qa,qb,x);
}

int qry (int l, int r, int val, int qa, int qb)
{
    if (qa<=l && r<=qb)
    {
        return lazy[val];
    }
    if (lazy[val]!=-1)
    {
        if (r!=l)
        {
            propagate(val,val*2);
            propagate(val,val*2+1);
        }
        lazy[val]=-1;
    }
    if (r<qa || l>qb)
        return inf;
    int mid,ans;
    mid=(l+r)/2;
    ans=inf;
    if (qa<=mid)
        ans=min(ans,qry(l,mid,val*2,qa,qb));
    if (qb>mid)
        ans=min(ans,qry(mid+1,r,val*2+1,qa,qb));
    return ans;
}

void build(int l, int r, int val)
{
    if (l==r)
    {
        aint[val]=finl[l];
        return;
    }
    int mid;
    mid=(l+r)/2;
    build(l,mid,val*2);
    build(mid+1,r,val*2+1);
    aint[val]=min(aint[val*2],aint[val*2+1]);
}

int que(int l, int r, int val, int qa, int qb)
{
    if (r<qa || l>qb)
        return inf;
    if (qa<=l && r<=qb)
        return aint[val];
    int mid,ans;
    mid=(l+r)/2;
    ans=inf;
    if (qa<=mid)
        ans=min(ans,que(l,mid,val*2,qa,qb));
    if (qb>mid)
        ans=min(ans,que(mid+1,r,val*2+1,qa,qb));
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n,q,i,j,t,q2,big,dif,y,res,cnt;
    bool ok;
    ok=true;
    cin >> n >> q;
    y=q;
    for (i=1; i<=q; i++)
    {
        cin >> query[i].l >> query[i].r >> query[i].x;
        aux2[i]=query[i];
        query2[i]=query[i];
    }
    sort(query+1,query+1+q,cmp);
    sort(query2+1,query2+1+q,cmp);
    t=0;
    for (j=1; j<=q; j++)
    {
        if (t==0 || query[j].x!=query[st[t]].x || (query[j].r<query[st[t]].l || query[j].l>query[st[t]].r))
        {
            t++;
            st[t]=j;
        }
        else
        {
            query[st[t]].l=max(query[st[t]].l,query[j].l);
            query[st[t]].r=min(query[st[t]].r,query[j].r);
        }
    }
    q2=q;
    q=t;
    while (t>0)
    {
        aux[t]=query[st[t]];
        t--;
    }
    for (j=1; j<=q; j++)
    {
        query[j]=aux[j];
        if (query[j].l==query[j-1].l && query[j].r==query[j-1].r && query[j].x!=query[j-1].x)
            ok=false;
    }
    t=0;
    for (j=1; j<=q2; j++)
    {
        ///cout << query2[j].l << " " << query2[j].r << " " << query2[j].x << "\n";
        if (t==0 || query2[j].x!=query2[st[t]].x || (query2[j].r<query2[st[t]].l || query2[j].l>query2[st[t]].r))
        {
            t++;
            st[t]=j;
        }
        else
        {
            query2[st[t]].l=min(query2[st[t]].l,query2[j].l);
            query2[st[t]].r=max(query2[st[t]].r,query2[j].r);
        }
    }
    q2=t;
    while (t>0)
    {
        aux[t]=query2[st[t]];
        t--;
    }
    for (j=1; j<=q2; j++)
    {
        query2[j]=aux[j];
        if (query2[j].l==query2[j-1].l && query2[j].r==query2[j-1].r && query2[j].x!=query2[j-1].x)
            ok=false;
    }
    /*
    build(1,n,1);
    for (j=1; j<=y; j++)
    {
        res=que(1,n,1,aux2[j].l+1,aux2[j].r+1);
        if (res!=aux2[j].x)
        {
            debug(aux2[j].l+1);
            debug(aux2[j].r+1);
            debug(aux2[j].x);
            debug(res);
        }
    }
    */
    for (j=0; j<=4*n; j++)
    {
        lazy[j]=-1;
    }
    for (j=1; j<=q2; j++)
    {
        lazy_update(1,n,1,query2[j].l+1,query2[j].r+1,query2[j].x);
    }
    for (j=1; j<=n; j++)
    {
        val[j].nr=qry(1,n,1,j,j);
        val[j].poz=j;
    }
    sort(val+1,val+1+n,cmp2);
    dif=0;
    cnt=q;
    for (j=1; j<=n; j++)
    {
        if (val[j].nr!=-1 && !placed[val[j].nr] && !used[val[j].poz] && query[cnt].l+1<=val[j].poz && query[cnt].r+1>=val[j].poz)
        {
            dif++;
            cnt--;
            placed[val[j].nr]=1;
            used[val[j].poz]=1;
            finl[val[j].poz]=val[j].nr;
        }
    }
    if (dif!=q)
        ok=false;
    big=n-1;
    for (j=1; j<=n; j++)
    {
        if (!used[val[j].poz])
        {
            while (big>=0 && placed[big])
            {
                big--;
            }
            if (big<val[j].nr)
            {
                ok=false;
                break;
            }
            placed[big]=1;
            used[val[j].poz]=1;
            finl[val[j].poz]=big;
        }
    }
    if (ok==false)
    {
        for (j=1; j<=n; j++)
        {
            cout << -1 << " ";
        }
    }
    else
    {
        for (j=1;j<=n;j++)
        {
             cout << finl[j] << " ";
        }
    }
    return 0;
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:159:30: warning: variable 'y' set but not used [-Wunused-but-set-variable]
  159 |     int n,q,i,j,t,q2,big,dif,y,res,cnt;
      |                              ^
rmq.cpp:159:32: warning: unused variable 'res' [-Wunused-variable]
  159 |     int n,q,i,j,t,q2,big,dif,y,res,cnt;
      |                                ^~~

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