fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. using ll = long long;
  7. using pii = pair<int,int>;
  8.  
  9. struct Line {
  10.     map<int,int> seg;
  11.  
  12.     // tách [x, ...] nếu cần và trả iterator tới đoạn bắt đầu tại x (hoặc vị trí chèn)
  13.     inline map<int,int>::iterator split(int x){
  14.         auto it = seg.lower_bound(x);
  15.         if (it != seg.end() && it->first == x) return it;
  16.         if (it == seg.begin()) return it;
  17.         auto pre = prev(it);
  18.         if (pre->second < x) return it;
  19.         if (pre->second == x-1) return it;
  20.         int l = pre->first, r = pre->second;
  21.         pre->second = x-1;
  22.         return seg.emplace_hint(it, x, r);
  23.     }
  24.  
  25.     // lật [l, r] và trả về delta chu vi trên line này
  26.     inline ll flip(int l, int r){
  27.         if (l > r) return 0;
  28.         auto itl = split(l), itr = split(r+1);
  29.         ll cover = 0;
  30.         int cur = l;
  31.  
  32.         // thu các đoạn đang tắt trong [l,r] để sau chèn lại (chính là “gaps”)
  33.         static vector<pii> add; add.clear(); add.reserve(8);
  34.         for (auto it = itl; it != itr; ++it){
  35.             int a = it->first, b = it->second;
  36.             if (cur < a) add.emplace_back(cur, a-1);
  37.             cover += (ll)(b - a + 1);
  38.             cur = b + 1;
  39.         }
  40.         if (cur <= r) add.emplace_back(cur, r);
  41.  
  42.         // xoá các đoạn đang bật trong [l,r]
  43.         seg.erase(itl, itr);
  44.  
  45.         // chèn lại các khoảng trống (giờ sẽ bật) dùng hint để O(1) amortized per insert
  46.         auto hint = seg.lower_bound(l);
  47.         for (auto &p : add) hint = seg.emplace_hint(hint, p.first, p.second);
  48.  
  49.         // delta chu vi trên line = |[l,r]| - 2 * (độ dài phần đã bật trong [l,r])
  50.         return (ll)(r - l + 1) - 2*cover;
  51.     }
  52. };
  53.  
  54. int main(){
  55.     ios::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57.  
  58.     int N, M, Q;
  59.     if(!(cin >> N >> M >> Q)) return 0;
  60.  
  61.     unordered_map<int, Line> hor, ver;           // hor: theo x (hàng), ver: theo y (cột)
  62.     hor.reserve(Q*2+16); ver.reserve(Q*2+16);
  63.     hor.max_load_factor(0.7f);
  64.     ver.max_load_factor(0.7f);
  65.  
  66.     auto get_h = [&](int i) -> Line& {
  67.         auto it = hor.find(i);
  68.         if (it == hor.end()) it = hor.emplace(i, Line()).first;
  69.         return it->second;
  70.     };
  71.     auto get_v = [&](int j) -> Line& {
  72.         auto it = ver.find(j);
  73.         if (it == ver.end()) it = ver.emplace(j, Line()).first;
  74.         return it->second;
  75.     };
  76.  
  77.     ll ans = 0;
  78.     while (Q--){
  79.         int x1,x2,y1,y2; cin >> x1 >> x2 >> y1 >> y2;
  80.         // 4 biên của hình chữ nhật
  81.         ans += get_h(x1-1).flip(y1, y2);
  82.         ans += get_h(x2).flip(y1, y2);
  83.         ans += get_v(y1-1).flip(x1, x2);
  84.         ans += get_v(y2).flip(x1, x2);
  85.         cout << ans << '\n';
  86.     }
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 5 4
1 4 2 5
1 2 3 4
2 3 4 5
1 4 3 5
stdout
copy 
16
20
24
22
https://ideone.com/MsQ7Qh
language:
C++14 (gcc 8.3)
created:
14 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!