CodeForces 60A

CodeForces 60A

题意：

给定一个序列，然后对其进行两种操作

1   L R W   代表从 a[L ] 到a[R] 全部加上W

2   L R W  代表从  a[L] 到 a[R] 中最大值为 W

问是否存在一个序灭满足上序操作  ， 操作数量小于5000

题解：

从尾往前跑  ，   维护序列每个值可存在的最大权值， 然后再从头往后跑，查询该序列是否满足要求

代码：

#include<stdio.h>
#define IF 1000000000
struct ode
{
    int flag, l, r, value;
}cun[5005];
int main()
{
    int Mark[5005], n, m, Mark2[5005];
    while(scanf(%d %d, &n, &m) != EOF)
    {
        for(int i = 0; i < 5005; i)
        Mark[i] = IF;
        int flag = 0;
        for(int i = 1; i <= m; i)
        scanf(%d %d %d %d, &cun[i].flag, &cun[i].l, &cun[i].r, & cun[i].value);
        for(int i = m; i >= 1; i--)
        {
            if(cun[i].flag == 1)
            for(int j = cun[i].l; j <= cun[i].r; j)
            {
                if(Mark[j] != IF)
                Mark[j] -= cun[i].value;
            }
            else
            {
                for(int j = cun[i].l; j <= cun[i].r; j)
                {
                    if(Mark[j] >= cun[i].value)
                    Mark[j] = cun[i].value;
                }
            }
        }
        for(int i = 1; i <= n; i)
        Mark2[i] = Mark[i];
        for(int i = 1; i <= m; i)
        {
            if(cun[i].flag == 1)
            for(int j = cun[i].l; j <= cun[i].r; j )
            Mark[j] = cun[i].value;
            else
            {
                int Max = -IF;
                for(int j = cun[i].l; j <= cun[i].r; j)
                {
                    if(Mark[j] > Max)   Max = Mark[j];
                }
                if(Max != cun[i].value)  { flag = 1; break;}
            }
        }
        if(flag)  {  printf(O\n);  continue;}
        else   printf(YES\n);
        for(int i = 1; i <= n; i)
        printf(%d , Mark2[i]);
        printf(\n);
    }
}