fork(2) download 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <map>
  4. using namespace std;
  5.  
  6. int n;
  7. int type[300005], a[300005], b[300005], c[300005];
  8. int res[300005];
  9. map<int, int> occ;
  10.  
  11. // Segment Tree 1
  12.  
  13. int t[600005];
  14.  
  15. int findmax(int p){
  16.     int res=2e9;
  17.     for (p+=n; p; p>>=1) res = min(res, t[p]);
  18.     return res;
  19. }
  20.  
  21. void upd(int l, int r, int x){
  22.     for(l+=n, r+=n; l<r; l>>=1, r>>=1){
  23.         if(l&1) t[l] = min(t[l], x), l++;
  24.         if(r&1) r--, t[r] = min(t[r], x);
  25.     }
  26.     return;
  27. }
  28.  
  29. // Segment Tree 2
  30.  
  31. int t2[600005];
  32.  
  33. int findmax(int l, int r){
  34.     int res = -2e9;
  35.     for(l+=n, r+=n; l<r; l>>=1, r>>=1){
  36.         if(l&1) res = max(res, t2[l++]);
  37.         if(r&1) res = max(res, t2[--r]);
  38.     }
  39.     return res;
  40. }
  41.  
  42. void updval(int p, int val){
  43.     for(t2[p+=n]=val; p>1; p>>=1) t2[p>>1] = max(t2[p], t2[p^1]);
  44.     return;
  45. }
  46.  
  47. // Main Solution
  48.  
  49. int main(){
  50.     int m;
  51.     scanf("%d%d", &n, &m);
  52.     for(int i=0; i<2*n; i++) t[i] = 2e9;
  53.     for(int i=0; i<n; i++) res[i] = (2e9)+1;
  54.     for(int i=0; i<m; i++){
  55.         scanf("%d", &type[i]);
  56.         if(type[i] == 1){
  57.             scanf("%d%d%d", &a[i], &b[i], &c[i]);
  58.             a[i]--, b[i]--;
  59.             upd(a[i], b[i]+1, c[i]);
  60.         } else{
  61.             scanf("%d%d", &a[i], &b[i]);
  62.             a[i]--;
  63.             if(res[a[i]] == (2e9)+1) res[a[i]] = findmax(a[i]);
  64.         }
  65.     }
  66.     for(int i=0; i<n; i++) if(res[i] == (2e9)+1) res[i] = findmax(i);
  67.  
  68.     // Check validity of the array
  69.     for(int i=0; i<n; i++) t2[n+i] = res[i];
  70.     for(int i=n-1; i>0; i--) t2[i] = max(t2[i<<1], t2[i<<1|1]);
  71.     for(int i=0; i<m; i++){
  72.         if(type[i] == 1){
  73.             if(findmax(a[i], b[i]+1) != c[i]){ printf("NO"); return 0; }
  74.         } else{
  75.             updval(a[i], b[i]);
  76.         }
  77.     }
  78.     for(int i=0; i<n; i++) if(res[i] < 0){ printf("NO"); return 0; }
  79.  
  80.     // Make the answer optimal
  81.     printf("YES\n");
  82.     for(int i=0; i<n; i++) occ[res[i]]++;
  83.     // - occ[2e9] >= 2 then the optimal OR result can simply be (1<<30)-1
  84.     if(occ[2e9] >= 2){
  85.         for(int i=0; i<n; i++) if(res[i] == 2e9){
  86.             res[i] = 1e9, occ[2e9]--;
  87.             if(occ[2e9] == 0) res[i] = (1<<29)-1;
  88.         }
  89.         for(int i=0; i<n; i++) printf("%d ", res[i]);
  90.         return 0;
  91.     }
  92.     // - otherwise, find the best value for the free 2e9 (if any)
  93.     int orresult = 0;
  94.     for(int i=0; i<n; i++){
  95.         if(res[i] == 0 || res[i] == 2e9) continue; // ignoring this could lead to a critical bug
  96.         occ[res[i]]--;
  97.         if(occ[res[i]]){
  98.             int temp=res[i], pow=0;
  99.             while(temp) pow++, temp /= 2;
  100.             res[i] = (1<<(pow-1))-1;
  101.         }
  102.         orresult |= res[i];
  103.     }
  104.     int tobe=0;
  105.     for(int cur=29; cur>=0; cur--){
  106.         if(orresult&(1<<cur)) continue;
  107.         if(tobe+(1<<cur) > 1e9) continue;
  108.         tobe += (1<<cur);
  109.     }
  110.     for(int i=0; i<n; i++){
  111.         if(res[i] == 2e9) printf("%d ", tobe);
  112.         else printf("%d ", res[i]);
  113.     }
  114.  
  115.     return 0;
  116. }
Success #stdin #stdout 0s 25784KB
comments (?)
stdin 
Standard input is empty
stdout 
YES
https://ideone.com/FfnJyp
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!