fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define li pair<long long , int>
  10. #define db double
  11. #define onBit(mask , i) (mask | (1 << i))
  12. #define offBit(mask , i) (mask & (~(1 << i)))
  13.  
  14. const long long MOD = 1e9 + 7;
  15. const int INF = 1e7;
  16. const int N = 1e3 + 7;
  17. long long BIT[N];
  18. int k , p;
  19. long long s[N][N] , a[21][N][N];
  20. int ans[N][N];
  21.  
  22. struct query{
  23.     int x1 , y1 , x2 , t , id;
  24.     long long w;
  25. };
  26.  
  27. vector<query> Query;
  28.  
  29. bool cmp(query x , query y){
  30.     if (x.t != y.t) return x.t < y.t;
  31.     if (x.y1 != y.y1) return x.y1 < y.y1;
  32.     return x.id > y.id;
  33. }
  34.  
  35. void ktao(){
  36.     for (int i = 1 ; i <= k ; ++i){
  37.         for (int j = 1 ; j <= k ; ++j){
  38.             s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
  39.             long long val = 0;
  40.             bool bl = 1;
  41.             for (int u = 0 ; u < 20 ; ++u){
  42.                 a[u][i][j] += a[u][i - 1][j] + a[u][i][j - 1] - a[u][i - 1][j - 1];
  43.                 if (a[u][i][j] * 2 == s[i][j]){
  44.                     val = 0;
  45.                     bl = 0;
  46.                 }
  47.                 if (!bl) continue;
  48.                 if (a[u][i][j] * 2 > s[i][j]) val += (1LL << u);
  49.             }
  50.             if (val == 0) continue;
  51.             query e;
  52.             e.x1 = i , e.y1 = j , e.x2 = 0 , e.t = val;
  53.             e.w = 0;
  54.             e.id = 0;
  55.             Query.push_back(e);
  56.         }
  57.     }
  58. }
  59.  
  60. void inp(){
  61.     cin >> k >> p;
  62.     for (int i = 1 ; i <= p ; ++i){
  63.         int x1 , y1 , x2 , y2 , t;
  64.         long long w;
  65.         cin >> x1 >> y1 >> x2 >> y2 >> t >> w;
  66.         s[x1][y1] += w;
  67.         s[x2 + 1][y1] -= w;
  68.         s[x1][y2 + 1] -= w;
  69.         s[x2 + 1][y2 + 1] += w;
  70.         for (int j = 0 ; j < 20 ; ++j) if (Bit(t , j)){
  71.             a[j][x1][y1] += w;
  72.             a[j][x2 + 1][y1] -= w;
  73.             a[j][x1][y2 + 1] -= w;
  74.             a[j][x2 + 1][y2 + 1] += w;
  75.         }
  76.         query e;
  77.         e.y1 = y1 , e.x1 = x1 , e.x2 = x2 , e.t = t;
  78.         e.w = w;
  79.         e.id = 1;
  80.         Query.push_back(e);
  81.         e.y1 = y2 + 1 , e.x1 = x1 , e.x2 = x2 , e.t = t;
  82.         e.w = w;
  83.         e.id = 2;
  84.         Query.push_back(e);
  85.     }
  86.     ktao();
  87.     sort(Query.begin() , Query.end() , cmp);
  88. //    for (int i = 0 ; i < Query.size() ; ++i){
  89. ////        cout << Query[i].id << " " << Query[i].y1 << " " << Query[i].x1 << " " << Query[i].x2 << " " << Query[i].t << '\n';
  90. //            cout << Query[i].id << " " << Query[i].y1 << " " << Query[i].t << '\n';
  91. //    }
  92. }
  93.  
  94. void update(int x , long long val){
  95.     while (x <= k){
  96.         BIT[x] += val;
  97.         x += x & -x;
  98.     }
  99. }
  100.  
  101. long long get(int x){
  102.     long long res = 0;
  103.     while (x > 0){
  104.         res += BIT[x];
  105.         x -= x & -x;
  106.     }
  107.     return res;
  108. }
  109.  
  110. void nl(int l , int r){
  111.     memset(BIT , 0 , sizeof BIT);
  112.     for (int i = l ; i <= r ; ++i){
  113.         if (Query[i].id == 1){
  114.             update(Query[i].x1 , Query[i].w);
  115.             update(Query[i].x2 + 1 , -Query[i].w);
  116.         }
  117.         if (Query[i].id == 2){
  118.             update(Query[i].x1 , -Query[i].w);
  119.             update(Query[i].x2 + 1 , +Query[i].w);
  120.         }
  121.         if (Query[i].id == 0){
  122.             long long tmp = get(Query[i].x1);
  123.             if (tmp * 2 > s[Query[i].x1][Query[i].y1]) ans[Query[i].x1][Query[i].y1] = Query[i].t;
  124.         }
  125.     }
  126. }
  127.  
  128. void solve(){
  129.     int i = 0;
  130.     while (i < Query.size()){
  131.         int j = i;
  132.         while (j < Query.size() - 1 && Query[j + 1].t == Query[i].t) ++j;
  133.         nl(i , j);
  134.         i = j + 1;
  135.     }
  136.     for (int i = 1 ; i <= k ; ++i){
  137.         for (int j = 1 ; j <= k ; ++j){
  138.             cout << ans[i][j] << " ";
  139.         }
  140.         cout << '\n';
  141.     }
  142. }
  143.  
  144. int main(){
  145. //    freopen("xhmax.inp" , "r" , stdin);
  146. //    freopen("xhmax.out" , "w" , stdout);
  147.     faster;
  148.     inp();
  149.     solve();
  150.     return 0;
  151. }
  152.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/78Y0vh
language:
C++14 (gcc 8.3)
created:
10 days 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!