Submission #5397

#	Time	Username	Problem	Language	Result	Execution time	Memory
5397		baneling100	Trading (IZhO13_trading)	C++98	100 / 100	244 ms	5184 KiB

trading

#include <stdio.h>

int n, m, nn, l, r, x, idx[1048576];

void index_tree(int left, int right, int now)
{
    int mid;

    if(l<=left && right<=r)
    {
        if(idx[now]<x+left-l)
            idx[now]=x+left-l;
    }
    else
    {
        mid=(left+right)/2;
        if(l<=mid)
            index_tree(left,mid,2*now);
        if(mid+1<=r)
            index_tree(mid+1,right,2*now+1);
    }
}

void input(void)
{
    int i;

    scanf("%d %d",&n,&m);
    for(nn=1 ; nn<n ; nn*=2);
    for(i=1 ; i<=m ; i++)
    {
        scanf("%d %d %d",&l,&r,&x);
        index_tree(1,nn,1);
    }
}

void clean(int left, int right, int now)
{
    int mid=(left+right)/2;

    if(left<right)
    {
        if(idx[now]>0)
        {
            if(idx[2*now]<idx[now])
                idx[2*now]=idx[now];
            if(idx[2*now+1]<idx[now]+mid-left+1)
                idx[2*now+1]=idx[now]+mid-left+1;
        }
        clean(left,mid,2*now);
        clean(mid+1,right,2*now+1);
    }
}

void output(void)
{
    int i;

    for(i=nn ; i<=nn+n-1 ; i++)
        printf("%d ",idx[i]);
}

int main(void)
{
    int i;

    input();
    clean(1,nn,1);
    output();

    return 0;
}

• Subtask 1: 100 / 100