fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define file "o"
  9. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  10. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  11. #define nl "\n"
  12. #define ss " "
  13. #define pb emplace_back
  14. #define fi first
  15. #define se second
  16. #define sz(s) (int)s.size()
  17. #define all(s) (s).begin(), (s).end()
  18. #define ms(a,x) memset(a, x, sizeof (a))
  19. #define cn continue
  20. #define re exit(0)
  21.  
  22. typedef long long ll;
  23. typedef unsigned long long ull;
  24. typedef long double ld;
  25. typedef vector<int> vi;
  26. typedef vector<ll> vll;
  27. typedef pair<int, int> pii;
  28. typedef pair<ll, ll> pll;
  29. typedef vector<pii> vpii;
  30. typedef vector<pll> vpll;
  31.  
  32. const int mod=1e9+7;
  33. const int maxn=2e5+15;
  34. const ll inf=4e18;
  35.  
  36. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  37. ll ran(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); }
  38.  
  39. inline void rf(){
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(nullptr); cout.tie(nullptr);
  42.     if(fopen(file".inp","r")){
  43.         freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  44.     }
  45. }
  46.  
  47. template<typename T> inline void add(T &x, const T &y){ x+=y; if(x>=mod) x-=mod; if(x<0) x+=mod; }
  48. template<typename T> inline bool maxi(T &a, T b){ if(a>=b) return 0; a=b; return 1; }
  49. template<typename T> inline bool mini(T &a, T b){ if(a<=b) return 0; a=b; return 1; }
  50.  
  51. int n, m, q;
  52.  
  53. template<class T>
  54. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  55.  
  56. struct line{
  57.     ordered_set<int> bp;
  58.     inline ll flip(int l, int r){
  59.         if(l>r) return 0;
  60.         ll cover=0;
  61.         bool on = (bp.order_of_key(l)&1);
  62.         auto it = bp.lower_bound(l);
  63.         int last=l;
  64.         while(it!=bp.end() && *it<=r){
  65.             int x=*it;
  66.             if(on) cover += x-last;
  67.             last=x;
  68.             ++it;
  69.             on=!on;
  70.         }
  71.         if(on) cover += (ll)r-last+1;
  72.         auto itl=bp.find(l);
  73.         if(itl==bp.end()) bp.insert(l); else bp.erase(itl);
  74.         auto itr=bp.find(r+1);
  75.         if(itr==bp.end()) bp.insert(r+1); else bp.erase(itr);
  76.         return (ll)(r-l+1)-2*cover;
  77.     }
  78. };
  79.  
  80. unordered_map<int, line> v, h;
  81.  
  82. inline line& get1(int i){
  83.     auto it=v.find(i);
  84.     if(it==v.end()) it=v.emplace(i, line()).fi;
  85.     return it->se;
  86. }
  87. inline line& get2(int j){
  88.     auto it=h.find(j);
  89.     if(it==h.end()) it=h.emplace(j, line()).fi;
  90.     return it->se;
  91. }
  92.  
  93. signed main(){
  94.     rf();
  95.     cin>>n>>m>>q;
  96.     v.reserve(q*2+15); h.reserve(q*2+15);
  97.     v.max_load_factor(0.7f); h.max_load_factor(0.7f);
  98.     ll ans=0;
  99.     while(q--){
  100.         int x1, x2, y1, y2; cin>>x1>>x2>>y1>>y2;
  101.         ans+=get1(x1-1).flip(y1, y2);
  102.         ans+=get1(x2).flip(y1, y2);
  103.         ans+=get2(y1-1).flip(x1, x2);
  104.         ans+=get2(y2).flip(x1, x2);
  105.         cout<<ans<<nl;
  106.     }
  107.     re;
  108. }
  109.  
Success #stdin #stdout 0.01s 5316KB
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/G4doVH
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!