fork(1) 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
stdin
Standard input is empty
stdout
YES