cf C. Levko and Array Recovery

http://codeforces.com/contest/361/problem/C
这道题倒着一次，然后正着一次，在正着的一次的时候判断合不合法就可以。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int inf=100000000;
 6 
 7 int p[1000001],ans[1000001];
 8 int t[1000001],l[1000001],r[1000001],d[1000001];
 9 int n,m;
10 int flag;
11 
12 int main()
13 {
14     while(scanf("%d%d",&n,&m)!=EOF)
15     {
16         for(int i=1; i<=n; i++)
17         {
18             ans[i]=inf;
19         }
20         for(int i=0; i<m; i++)
21         {
22             scanf("%d%d%d%d",&t[i],&l[i],&r[i],&d[i]);
23         }
24         for(int i=m-1; i>=0; i--)
25         {
26             if(t[i]==1)
27             {
28                 for(int j=l[i]; j<=r[i]; j++)
29                 {
30                     ans[j]-=d[i];
31                 }
32             }
33             else if(t[i]==2)
34             {
35                 for(int j=l[i]; j<=r[i]; j++)
36                 {
37                     ans[j]=min(ans[j],d[i]);
38                 }
39             }
40         }
41         for(int i=1; i<=n; i++)
42         {
43             p[i]=ans[i];
44         }
45         bool flag1=false;
46         for(int i=0; i<m; i++)
47         {
48             if(t[i]==1)
49             {
50                 for(int j=l[i]; j<=r[i]; j++)
51                 {
52                     p[j]+=d[i];
53                 }
54             }
55             else if(t[i]==2)
56             {
57                 flag=0;
58                 for(int j=l[i]; j<=r[i]; j++)
59                 {
60                     if(p[j]==d[i]) flag=1;
61                     else if(p[j]>d[i])
62                     {
63                         flag1=true;
64                         break;
65                     }
66                 }
67                 if(flag!=1)
68                 {
69                     flag1=true;
70                     break;
71                 }
72             }
73         }
74         if(flag1) printf("NO
");
75         else
76         {
77             printf("YES
");
78             for(int i=1; i<=n; i++)
79             {
80                 if(i==1)
81                     printf("%d",ans[i]);
82                 else printf(" %d",ans[i]);
83             }
84             printf("
");
85         }
86     }
87     return 0;
88 }
View Code