Submission #423584

#	Time	Username	Problem	Language	Result	Execution time	Memory
423584		Amylopectin	RMQ (NOI17_rmq)	C++14	100 / 100	64 ms	4668 KiB

rmq

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int mxn = 4e5 + 10;
struct we
{
    int fr,to,vaa;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.vaa > r.vaa;
}
struct we a[mxn] = {};
int se[mxn] = {},fou,ofo,ta[mxn] = {},u[mxn] = {};
int fima(int l,int r)
{
    if(l > r)
        return l;
    return r;
}
int fimi(int l,int r)
{
    if(l < r)
        return l;
    return r;
}
int ins(int cl,int cr,int no,int tn)
{
    if(cr < tn || cl > tn)
    {
        return 0;
    }
    if(cl == cr)
    {
        se[no] = 1;
        return 0;
    }
    int mid = (cl+cr) / 2;
    ins(cl,mid,no*2,tn);
    ins(mid+1,cr,no*2+1,tn);
    se[no] = se[no*2] + se[no*2+1];
    return 0;
}
int fine(int cl,int cr,int no,int tn)
{
    if(cr <= tn)
    {
        return 0;
    }
    if(se[no] == (cr-cl+1))
    {
        return 0;
    }
    if(cl == cr)
    {
        ofo = 1;
        fou = cl;
        return 0;
    }
    int mid = (cl+cr) / 2;
    fine(cl,mid,no*2,tn);
    if(ofo == 1)
    {
        return 0;
    }
    fine(mid+1,cr,no*2+1,tn);
    return 0;
}
int main()
{
    int i,j,n,m,ru = 0,be,cl,cr,bl,br,of = 0,fba;
    scanf("%d %d",&n,&m);
    for(i=0; i<m; i++)
    {
        scanf("%d %d %d",&a[i].fr,&a[i].to,&a[i].vaa);
    }
    sort(a,a+m,cmp);
    fba = n-1;
    for(i=0; i<n; i++)
    {
        ta[i] = -1;
    }
    while(ru < m)
    {
        be = ru;
        cl = a[ru].fr;
        cr = a[ru].to;
        bl = cl;
        br = cr;
        ru ++;
        while(ru < m && a[ru].vaa == a[be].vaa)
        {
            cl = fima(cl,a[ru].fr);
            bl = fimi(bl,a[ru].fr);
            cr = fimi(cr,a[ru].to);
            br = fima(br,a[ru].to);
            ru ++;
        }
        if(cl > cr)
        {
            of = 1;
            break;
        }
        ofo = 0;
        fine(0,n-1,1,cl-1);
        if(ofo == 0 || fou > cr)
        {
            of = 1;
            break;
        }
        ta[fou] = a[be].vaa;
        u[a[be].vaa] = 1;
        ins(0,n-1,1,fou);
        for(j=bl; j<=br; j++)
        {
            if(ta[j] != -1)
            {
                ofo = 0;
                fine(0,n-1,1,j);
                if(ofo == 0)
                {
                    break;
                }
                j = fou;
                if(j > br)
                {
                    break;
                }
            }
            while(u[fba] == 1)
            {
                fba --;
            }
            ta[j] = fba;
            u[fba] = 1;
            if(fba < a[be].vaa)
            {
                of = 1;
                break;
            }
            ins(0,n-1,1,j);
        }
        if(of == 1)
        {
            break;
        }
    }
    if(of == 1)
    {
        for(i=0; i<n; i++)
        {
            printf("-1 ");
        }
        return 0;
    }
    for(i=0; i<n; i++)
    {
        if(ta[i] == -1)
        {
            while(u[fba] == 1)
            {
                fba --;
            }
            ta[i] = fba;
            u[fba] = 1;
        }
    }
    for(i=0; i<n; i++)
    {
        printf("%d ",ta[i]);
    }
    return 0;
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
rmq.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d %d %d",&a[i].fr,&a[i].to,&a[i].vaa);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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