Advertisement
FHVirus

Untitled

Oct 22nd, 2021
1,063
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.66 KB | None | 0 0
  1. // Knapsack DP is harder than FFT.
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
  5. #define ff first
  6. #define ss second
  7. #define pb emplace_back
  8. #define AI(x) begin(x),end(x)
  9. template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
  10. template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;}
  11. #ifdef OWO
  12. #define debug(args...) SDF(#args, args)
  13. #define OIU(args...) ostream& operator<<(ostream&O,args)
  14. #define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
  15. LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
  16. template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
  17. template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
  18. #else
  19. #pragma GCC optimize("Ofast")
  20. #define debug(...) ((void)0)
  21. #endif
  22.  
  23. struct LISAN : vector<int> {
  24.     void done() { sort(AI()); erase(unique(AI()), end()); }
  25.     int operator () (int v) { return lower_bound(AI(), v) - begin(); }
  26. };
  27. struct BIT {
  28.     int n; vector<int> val;
  29.     BIT (int n = 0) : n(n), val(n+1, 0) {}
  30.     void modify(int p, int v){
  31.         for(++p; p <= n; p += p&-p)
  32.             val[p] += v;
  33.     }
  34.     int query(int p){
  35.         int r = 0;
  36.         for(++p; p > 0; p -= p&-p)
  37.             r += val[p];
  38.         return r;
  39.     }
  40.     int query(int l, int r){
  41.         return query(r) - query(l-1);
  42.     }
  43. };
  44.  
  45. signed main(){
  46.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  47.     int n; cin >> n;
  48.     vector<tuple<int, int, int>> ver, hor;
  49.     LISAN lx, ly;
  50.     for(int x1, y1, x2, y2, i = 0; i < n; ++i){
  51.         cin >> x1 >> y1 >> x2 >> y2;
  52.         lx.pb(x1); if(x1 != x2) lx.pb(x2);
  53.         ly.pb(y1); if(y1 != y2) ly.pb(y2);
  54.         if(x1 == x2) ver.pb(x1, y1, y2);
  55.         else hor.pb(y1, x1, x2);
  56.     }
  57.     lx.done(); ly.done();
  58.     for(auto &[x, y1, y2]: ver){ x = lx(x); y1 = ly(y1); y2 = ly(y2); }
  59.     for(auto &[y, x1, x2]: hor){ y = ly(y); x1 = lx(x1); x2 = lx(x2); }
  60.  
  61.     vector<vector<pii>> mods(ly.size() + 1);
  62.     BIT bit(lx.size() + 1);
  63.     for(auto [x, y1, y2]: ver){
  64.         mods[y1].pb(x,  1);
  65.         mods[y2].pb(x, -1);
  66.     }
  67.     int ptr = -1;
  68.     ll ans = 0;
  69.     for(auto [y, x1, x2]: hor){
  70.         while(ptr < y){
  71.             ++ptr;
  72.             for(auto [p, v]: mods[ptr])
  73.                 bit.modify(p, v);
  74.         }
  75.         ans += bit.query(x1, x2);
  76.     }
  77.     cout << ans << '\n';
  78.     return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement