FHVirus

CSES Robot Path Burn Chicken

Oct 22nd, 2021
1,048
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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<ll> {
  24.     void done() { sort(AI()); erase(unique(AI()), end()); }
  25.     int operator () (ll 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 init(){ fill(AI(val), 0); };
  31.     void modify(int p, int v){
  32.         for(++p; p <= n; p += p & -p)
  33.             val[p] += v;
  34.     }
  35.     int query(int p){
  36.         int r = 0;
  37.         for(++p; p > 0; p -= p&-p)
  38.             r += val[p];
  39.         return r;
  40.     }
  41.     int query(int l, int r){
  42.         return query(r) - query(l-1);
  43.     }
  44. };
  45. struct SOLVER {
  46.     int dx, dy, tot;
  47.     vector<vector<pii>> mods, ques, vers;
  48.     BIT bit;
  49.     SOLVER (int dx = 0, int dy = 0):
  50.         dx(dx), dy(dy), mods(dy+1), ques(dy+1), vers(dx+1), bit(dx+1), tot(0) {}
  51.     void init(){
  52.         for(int i = 0; i <= dy; ++i) mods[i].clear();
  53.         for(int i = 0; i <= dy; ++i) ques[i].clear();
  54.         for(int i = 0; i <= dx; ++i) vers[i].clear();
  55.         bit.init();
  56.         tot = 0;
  57.     }
  58.     void add(int x1, int y1, int x2, int y2){
  59.         ++tot;
  60.         if(x1 == x2){
  61.             if(y1 > y2) swap(y1, y2);
  62.             mods[y1].pb(x1, 1);
  63.             mods[y2+1].pb(x1, -1);
  64.             vers[x1].pb(y1, y2);
  65.         } else {
  66.             if(x1 > x2) swap(x1, x2);
  67.             ques[y1].pb(x1, x2);
  68.         }
  69.     }
  70.     bool go(vector<pii> &v){
  71.         if(v.size() <= 1) return false;
  72.         sort(AI(v));
  73.         int mx = -1;
  74.         for(auto [l, r]: v){
  75.             if(mx >= l) return true;
  76.             mx = max(mx, r);
  77.         }
  78.         return false;
  79.     }
  80.     bool solve(){
  81.         for(auto &i: ques) if(go(i)) return true;
  82.         for(auto &i: vers) if(go(i)) return true;
  83.         ll cnt = 0;
  84.         for(int i = 0; i <= dy; ++i){
  85.             for(auto [p, v]: mods[i])
  86.                 bit.modify(p, v);
  87.             for(auto [l, r]: ques[i])
  88.                 cnt += bit.query(l, r);
  89.             if(cnt >= tot) return true;
  90.         }
  91.         return false;
  92.     }
  93. };
  94.  
  95. typedef array<ll, 4> seg;
  96. ll banana(seg a, seg b, LISAN &lx, LISAN &ly){
  97.     if((a[0] == a[2]) and (b[0] == b[2])){
  98.         if(a[0] != b[0]) return -1;
  99.         return min(abs(ly[a[1]] - ly[b[1]]), abs(ly[a[1]] - ly[b[3]]));
  100.     }
  101.     if((a[1] == a[3]) and (b[1] == b[3])){
  102.         if(a[1] != b[1]) return -1;
  103.         return min(abs(lx[a[0]] - lx[b[0]]), abs(lx[a[0]] - lx[b[2]]));
  104.     }
  105.     if(a[0] == a[2]) return abs(ly[a[1]] - ly[b[1]]);
  106.     return abs(lx[a[0]] - lx[b[0]]);
  107. }
  108.  
  109. bool opposite(char a, char b){
  110.     if(a > b) swap(a, b);
  111.     return (a == 'D' and b == 'U')
  112.         or (a == 'L' and b == 'R');
  113. }
  114.  
  115. signed main(){
  116.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  117.     int n; cin >> n;
  118.     vector<ll> len;
  119.     vector<pair<char, ll>> mv;
  120.     int ret = n+1;
  121.     for(int i = 0; i < n; ++i){
  122.         char d; int x; cin >> d >> x;
  123.         if(i > 0 and d == mv.back().ff){
  124.             mv.back().ss += x;
  125.             len.back() += x;
  126.         } else {
  127.             if(i > 0 and opposite(mv.back().ff, d))
  128.                 ret = min(i, ret);
  129.             mv.pb(d, x);
  130.             len.pb(x);
  131.         }
  132.     }
  133.     n = len.size();
  134.  
  135.     vector<seg> segs;
  136.     LISAN lx, ly; lx.pb(0), ly.pb(0);
  137.     for(ll cx = 0, cy = 0, nx, ny, i = 0; i < n; ++i){
  138.         auto [dir, x] = mv[i];
  139.         if(dir == 'U') nx = cx, ny = cy + x;
  140.         if(dir == 'D') nx = cx, ny = cy - x;
  141.         if(dir == 'R') nx = cx + x, ny = cy;
  142.         if(dir == 'L') nx = cx - x, ny = cy;
  143.         segs.push_back({ cx, cy, nx, ny });
  144.         if(cx != nx) lx.pb(nx);
  145.         if(cy != ny) ly.pb(ny);
  146.         cx = nx, cy = ny;
  147.     }
  148.     lx.done(); ly.done();
  149.     for(auto &a: segs){
  150.         a[0] = lx(a[0]); a[2] = lx(a[2]);
  151.         a[1] = ly(a[1]); a[3] = ly(a[3]);
  152.     }
  153.  
  154.     int l = 1, r = n, m;
  155.     SOLVER solver(lx.size(), ly.size());
  156.     while(l < r){
  157.         m = (l+r) / 2;
  158.         solver.init();
  159.         for(int i = 0; i <= m; ++i)
  160.             solver.add(segs[i][0], segs[i][1], segs[i][2], segs[i][3]);
  161.         if(solver.solve()) r = m;
  162.         else l = m+1;
  163.         if(l >= ret) break;
  164.     }
  165.    
  166.     ll sum = accumulate(begin(len), begin(len) + min(ret, l), 0ll);
  167.     if(l == n or ret <= l){
  168.         cout << sum << '\n';
  169.         return 0;
  170.     }
  171.     debug(sum);
  172.     ll ans = 1e18;
  173.     for(int i = 0; i < l-1; ++i){
  174.         ll d = banana(segs[l], segs[i], lx, ly);
  175.         if(d != -1) ans = min(ans, d);
  176.     }
  177.     cout << sum + ans << '\n';
  178.     return 0;
  179. }
  180.  
RAW Paste Data