fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. void build(int *seg, int *a, int start, int end, int node)
  6. {
  7.     if(start>end)
  8.         return;
  9.     if(start == end)
  10.     {
  11.         seg[node] = a[start];
  12.         return;
  13.     }
  14.     int mid = (start+end)>>1;
  15.     build (seg, a, start, mid, 2*node+1);
  16.     build (seg, a, mid+1, end, 2*node+2);
  17.  
  18.     seg[node] = min(seg[2*node+1], seg[2*node+2]);
  19. }
  20.  
  21. int query (int *seg, int l, int r, int start, int end, int node)
  22. {
  23.     if(r<start || end<l || l>r)
  24.         return INT_MAX;
  25.     if(start>=l && end<=r)
  26.     {
  27.         return seg[node];
  28.     }
  29.     int mid = (start+end)>>1;
  30.     int q1 = query (seg, l, r, start, mid, 2*node+1);
  31.     int q2 = query (seg, l, r, mid+1, end, 2*node+2);
  32.  
  33.     return min(q1,q2);
  34. }
  35.  
  36. int main() 
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(NULL);
  40.  
  41.     int n=0, q=0;
  42.     cin>>n>>q;
  43.  
  44.     int sz = n<<2;
  45.     int seg[sz]; int a[n];
  46.     fill(seg, seg + sz, INT_MAX);
  47.  
  48.     for(int i=0; i<n; i++)
  49.         cin>>a[i];
  50.     vector < pair <int, int> > v(q+1); // derived range for each query {start, end}
  51.     //fill (v.begin(), v.end(), {-1,-1});
  52.     for(int i=0; i<=q; i++)
  53.         v[i].first = v[i].second = -1;
  54.  
  55.     for(int i=0; i<n; i++)
  56.     {
  57.         if(v[a[i]].first == -1)
  58.             v[a[i]].first = i;
  59.         else
  60.             v[a[i]].second = i;
  61.     }
  62.  
  63.     for(int i=0; i<=q; i++)
  64.     {
  65.         if(v[i].first !=-1 && v[i].second == -1)
  66.             v[i].second = v[i].first;
  67.         //cout<<i<<" "<<v[i].first<<" "<<v[i].second<<endl;
  68.     }
  69.  
  70.     build(seg, a, 0, n-1, 0);
  71.  
  72.     int flag = 0;
  73.     for(int i=q; i>=0; i--)
  74.     {
  75.         if(v[i].first !=-1 && v[i].second != -1)
  76.         {
  77.             //cout<<v[i].first<<" "<<v[i].second<<endl;
  78.             int qry = query(seg, v[i].first, v[i].second, 0, n-1, 0);
  79.             //cout<<qry<<endl;
  80.             if(i > qry && qry!=0)
  81.             {
  82.                 cout<<"NO"<<endl; flag = 1; break;
  83.             }
  84.         }
  85.     }
  86.     if(flag == 0)
  87.     {
  88.         int z_flag =0;
  89.         for(int i=0; i<n; i++)
  90.         {
  91.             if(a[i]==0)
  92.             {
  93.                 int l=-1, r=-1, j=i+1;
  94.                 while(j<n)
  95.                 {
  96.                     if(a[j]!=0)
  97.                     {
  98.                         r = j; break;
  99.                     }
  100.                     else
  101.                         ++j;
  102.                 }
  103.                 j= i-1;
  104.                 while(j>=0)
  105.                 {
  106.                     if(a[j]!=0)
  107.                     {
  108.                         l = j; break;
  109.                     }
  110.                     else
  111.                         --j;
  112.                 }
  113.                 if( l==-1 && r==-1)
  114.                 {
  115.                     z_flag=1; break;
  116.                 }
  117.                 else if(r==-1)
  118.                 {
  119.                     for(j = l+1; j<n; j++)
  120.                         a[j]=a[l];
  121.                     break;
  122.                 }
  123.                 else if(l==-1)
  124.                 {
  125.                     for(j= r-1; j>=0; j--)
  126.                         a[j] = a[r];
  127.                     i = r;
  128.                 }
  129.                 else if( r!=-1 && l!=-1)
  130.                 {
  131.                     for(j = l+1; j<r; j++)
  132.                         a[j]=a[r];
  133.                     i=r;
  134.                 }
  135.             }
  136.         }
  137.         //cout<<z_flag<<endl;
  138.         cout<<"YES"<<endl;
  139.         if(z_flag==1)
  140.         {
  141.             for(int i=0; i<n; i++)
  142.                 cout<<q<<" ";
  143.             cout<<endl;
  144.         }
  145.         else
  146.         {
  147.             for(int i=0; i<n; i++)
  148.                 cout<<a[i]<<" ";
  149.             cout<<endl;
  150.         }
  151.     }
  152. 	return 0;
  153. }
Success #stdin #stdout 0s 4548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/im4uvZ
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!