fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Interval set: map<L, R> for disjoint, merged intervals (both inclusive)
  5. struct IntervalSet {
  6.     // All intervals are within [1..LEN]; initially empty (all zeros)
  7.     int LEN;
  8.     map<int,int> seg;
  9.  
  10.     IntervalSet(int LEN_=0): LEN(LEN_) {}
  11.  
  12.     // split at pos: ensure there's an interval starting at pos; return iterator to interval with start >= pos
  13.     map<int,int>::iterator split(int pos){
  14.         if(pos > LEN) return seg.end();
  15.         auto it = seg.upper_bound(pos);
  16.         if(it==seg.begin()) return it;
  17.         --it;
  18.         int L = it->first, R = it->second;
  19.         if(R < pos) return ++it;
  20.         if(L == pos) return it;
  21.         // [L, R] -> [L, pos-1] and [pos, R]
  22.         it->second = pos-1;
  23.         return seg.emplace(pos, R).first;
  24.     }
  25.  
  26.     // query sum of 1s in [l, r]
  27.     long long range_one_len(int l, int r){
  28.         if(l>r) return 0;
  29.         auto itl = split(l);
  30.         auto itr = split(r+1);
  31.         long long res = 0;
  32.         for(auto it=itl; it!=itr; ++it){
  33.             res += (long long)it->second - it->first + 1;
  34.         }
  35.         return res;
  36.     }
  37.  
  38.     // toggle [l, r]: remove ones inside and add the gaps (complement inside)
  39.     void toggle(int l, int r){
  40.         if(l>r) return;
  41.         auto itl = split(l);
  42.         auto itr = split(r+1);
  43.  
  44.         // collect existing 1-intervals and build the complement gaps within [l,r]
  45.         vector<pair<int,int>> old1;        // to erase
  46.         vector<pair<int,int>> add1;        // to insert (gaps)
  47.         int cur = l;
  48.         for(auto it=itl; it!=itr; ++it){
  49.             int a = it->first, b = it->second;
  50.             if(cur <= a-1) add1.push_back({cur, a-1});
  51.             old1.push_back({a,b});
  52.             cur = b+1;
  53.         }
  54.         if(cur <= r) add1.push_back({cur, r});
  55.  
  56.         // erase old ones
  57.         seg.erase(itl, itr);
  58.         // insert gaps and merge if needed
  59.         for(auto [a,b]: add1){
  60.             if(a>b) continue;
  61.             // try merge with prev
  62.             auto it = seg.lower_bound(a);
  63.             int L=a, R=b;
  64.             if(it!=seg.begin()){
  65.                 auto itp = prev(it);
  66.                 if(itp->second+1 >= L){
  67.                     L = itp->first;
  68.                     R = max(R, itp->second);
  69.                     seg.erase(itp);
  70.                 }
  71.             }
  72.             while(it!=seg.end() && it->first<=R+1){
  73.                 R = max(R, it->second);
  74.                 it = seg.erase(it);
  75.             }
  76.             seg.emplace(L,R);
  77.         }
  78.     }
  79. };
  80.  
  81. // two families of lines:
  82. //   col[x] for vertical borders between column x and x+1  (x=0..N), length M
  83. //   row[y] for horizontal borders between row y and y+1   (y=0..M), length N
  84. int main(){
  85.     ios::sync_with_stdio(false);
  86.     cin.tie(nullptr);
  87.  
  88.     int N,M,Q;
  89.     if(!(cin>>N>>M>>Q)) return 0;
  90.  
  91.     unordered_map<int, IntervalSet> col, row;
  92.     col.reserve(Q*4); row.reserve(Q*4);
  93.  
  94.     auto get_col = [&](int x)->IntervalSet&{
  95.         auto it = col.find(x);
  96.         if(it==col.end()) it = col.emplace(x, IntervalSet(M)).first;
  97.         return it->second;
  98.     };
  99.     auto get_row = [&](int y)->IntervalSet&{
  100.         auto it = row.find(y);
  101.         if(it==row.end()) it = row.emplace(y, IntervalSet(N)).first;
  102.         return it->second;
  103.     };
  104.  
  105.     long long perim = 0;
  106.  
  107.     for(int i=0;i<Q;i++){
  108.         int x1,x2,y1,y2;
  109.         cin>>x1>>x2>>y1>>y2;
  110.  
  111.         // left vertical boundary at x1-1
  112.         {
  113.             auto &S = get_col(x1-1);
  114.             long long k = S.range_one_len(y1,y2);
  115.             S.toggle(y1,y2);
  116.             perim += (y2-y1+1) - 2*k;
  117.         }
  118.         // right vertical boundary at x2
  119.         {
  120.             auto &S = get_col(x2);
  121.             long long k = S.range_one_len(y1,y2);
  122.             S.toggle(y1,y2);
  123.             perim += (y2-y1+1) - 2*k;
  124.         }
  125.         // top horizontal boundary at y1-1
  126.         {
  127.             auto &S = get_row(y1-1);
  128.             long long k = S.range_one_len(x1,x2);
  129.             S.toggle(x1,x2);
  130.             perim += (x2-x1+1) - 2*k;
  131.         }
  132.         // bottom horizontal boundary at y2
  133.         {
  134.             auto &S = get_row(y2);
  135.             long long k = S.range_one_len(x1,x2);
  136.             S.toggle(x1,x2);
  137.             perim += (x2-x1+1) - 2*k;
  138.         }
  139.  
  140.         cout << perim << "\n";
  141.     }
  142.     return 0;
  143. }
  144.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
4 5 4
1 4 2 5
1 2 3 4
2 3 4 5
1 4 3 5
stdout 
16
20
24
22
https://ideone.com/W8OKGj
language:
C++14 (gcc 8.3)
created:
8 hours 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!