Advertisement
YEZAELP

o59_oct_c1_table

Dec 20th, 2021
748
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int inf = 1e9;
  5. const int N = 3e2 + 10;
  6. const int M = 5e3 + 10;
  7. const int logM = ceil(log2(M));
  8. int table[N][1 << (logM + 1)], lazy[N][1 << (logM + 1)];
  9. int n, m;
  10.  
  11. void Lazy(int idx, int row, int l, int r){
  12.     if(lazy[row][idx] == 0) return;
  13.     if(l != r){
  14.         lazy[row][2 * idx] = lazy[row][idx];
  15.         lazy[row][2 * idx + 1] = lazy[row][idx];
  16.     }
  17.     table[row][idx] = lazy[row][idx];
  18.     lazy[row][idx] = 0;
  19. }
  20.  
  21. void Update(int idx, int l, int r, int row, int s, int e, int val){
  22.     Lazy(idx, row, l, r);
  23.     if(l > e or r < s) return;
  24.     if(s <= l and r <= e){
  25.         if(l != r){
  26.             lazy[row][2 * idx] = val;
  27.             lazy[row][2 * idx + 1] = val;
  28.         }
  29.         table[row][idx] = val;
  30.         return;
  31.     }
  32.     int mid = (l + r) / 2;
  33.     Update(2 * idx, l, mid, row, s, e, val);
  34.     Update(2 * idx + 1, mid + 1, r, row, s, e, val);
  35.     if(l != r) table[row][idx] = min(table[row][2 * idx], table[row][2 * idx + 1]);
  36. }
  37.  
  38. int Query(int idx, int l, int r, int row, int s, int e){
  39.     Lazy(idx, row, l, r);
  40.     if(l > e or r < s) return inf;
  41.     if(s <= l and r <= e) return table[row][idx];
  42.     int mid = (l + r) / 2;
  43.     return min( Query(2 * idx, l, mid, row, s, e),
  44.                 Query(2 * idx + 1, mid + 1, r, row, s, e));
  45. }
  46.  
  47. int main(){
  48.  
  49.     int Q;
  50.     scanf("%d %d %d", &n, &m, &Q);
  51.  
  52.     for(int q=1;q<=Q;q++){
  53.         int k; scanf("%d", &k);
  54.         if(k == 1){
  55.             int r, c, x; scanf("%d %d %d", &r, &c, &x);
  56.             Update(1, 1, m, r, c, c, x);
  57.         }
  58.         else if(k == 2){
  59.             int r, x; scanf("%d %d", &r, &x);
  60.             Update(1, 1, m, r, 1, m, x);
  61.         }
  62.         else if(k == 3){
  63.             int r, c; scanf("%d %d", &r, &c);
  64.             printf("%d\n", Query(1, 1, m, r, c, c));
  65.         }
  66.         else if(k == 4){
  67.             int mn = inf;
  68.             for(int i=1;i<=n;i++){
  69.                 mn = min(mn, Query(1, 1, m, i, 1, m));
  70.             }
  71.             printf("%d\n", mn);
  72.         }
  73.     }
  74.  
  75.     return 0;
  76. }
Advertisement
RAW Paste Data Copied
Advertisement