fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) (x).begin(), (x).end()
  4.  
  5. #ifdef KAZAR
  6.     #define eprintf(...) fprintf(stderr,__VA_ARGS__)
  7. #else
  8.     #define eprintf(...) 0
  9. #endif
  10.  
  11. using namespace std;
  12.  
  13. template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
  14. template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
  15. template<class T> inline T abs(T a){return a>0 ? a : -a;}
  16. template<class T> inline T gcd(T a,T b){return __gcd(a, b);}
  17. template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}
  18.  
  19. typedef long long ll;
  20. typedef pair<int, int> ii;
  21.  
  22. const int inf = 1e9 + 143;
  23. const ll longinf = 1e18 + 143;
  24.  
  25. inline int read(){int x;scanf(" %d",&x);return x;}
  26.  
  27. const int N = 3e5 + 100;
  28.  
  29. int n;
  30. char p1[N], p2[N];
  31. int x1[N], x2[N];
  32. vector<int> xs;
  33.  
  34. inline int getid(int x){
  35.     return lower_bound(all(xs), x) - xs.begin();
  36. }
  37.  
  38. int cnt_start[N], cnt_end[N];
  39. ll lf[N], rg[N];
  40.  
  41. void pre(){
  42.     for(int i = 1; i <= n; i++){
  43.         if(p1[i] == p2[i])
  44.             continue;
  45.         cnt_start[getid(x1[i])]++;
  46.         cnt_end[getid(x2[i])]++;
  47.     }
  48.     int sz = xs.size();
  49.     {
  50.         ll sumx = 0;
  51.         int cnt = 0;
  52.         for(int i = 0; i < sz; i++){
  53.             lf[i] += (ll)xs[i] * cnt - sumx;
  54.             sumx += (ll)xs[i] * cnt_end[i];
  55.             cnt += cnt_end[i];
  56.         }
  57.     }{
  58.         ll sumx = 0;
  59.         int cnt = 0;
  60.         for(int i = sz - 1; i >= 0; i--){
  61.             rg[i] += sumx - (ll)xs[i] * cnt;
  62.             sumx += (ll)xs[i] * cnt_start[i];
  63.             cnt += cnt_start[i];
  64.         }
  65.     }
  66. }
  67.  
  68. ll solve_one(){
  69.     ll res = longinf;
  70.     for(int i = 0; i < xs.size(); i++){
  71.         umin(res, lf[i] + rg[i]);
  72.     }
  73.     return res;
  74. }
  75.  
  76. class fenwick{
  77. public:
  78.     ll f[N];
  79.     void add(int x,ll v){
  80.         ++x;
  81.         while(x < N){
  82.             f[x] += v;
  83.             x += x & -x;
  84.         }
  85.     }
  86.     ll get(int l,int r){
  87.         if(l > r)
  88.             return 0;
  89.         ++l; ++r;
  90.         ll res = 0;
  91.         for(int i = r; i > 0; i -= i & -i)
  92.             res += f[i];
  93.         for(int i = l - 1; i > 0; i -= i & -i)
  94.             res -= f[i];
  95.         return res;
  96.     }
  97. };
  98.  
  99. int L, R;
  100. fenwick sumx1, sumx2, cnt;
  101.  
  102. void add(int x1,int x2,int c){
  103.     int id = getid(x1 + x2);
  104.     sumx1.add(id, x1 * c);
  105.     sumx2.add(id, x2 * c);
  106.     cnt.add(id, c);
  107. }
  108.  
  109. int used[N];
  110. vector<ii> vends[N];
  111. vector<ii> vbegs[N];
  112.  
  113. void addL(int l,int r,int c){
  114.     for(int i = 0; i < vends[l].size(); i++){
  115.         int v = vends[l][i].first;
  116.         if(v > xs[r]) break;
  117.         used[vends[l][i].second] = c;
  118.         add(xs[l], v, c);
  119.     }
  120. }
  121.  
  122. void addR(int l,int r,int c){
  123.     for(int i = 0; i < vbegs[r].size(); i++){
  124.         int v = vbegs[r][i].first;
  125.         if(v < xs[l]) break;
  126.         used[vbegs[r][i].second] = c;
  127.         add(v, xs[r], c);
  128.     }
  129. }
  130.  
  131. ll ans = longinf;
  132.  
  133. void init(){
  134.     L = 0, R = 0;
  135.     addL(0, 0, +1);
  136. }
  137.  
  138. void fix(int l,int r){
  139.     while(R < r) addR(L, ++R, +1);
  140.     while(R > r) addR(L, R--, -1);
  141.     while(L > l) addL(--L, R, +1);
  142.     while(L < l) addL(L++, R, -1);
  143. }
  144.  
  145. int cL = 0, cR = 0;
  146.  
  147. ll calc(int l,int r){
  148.     int sz = xs.size();
  149.     ll res = lf[l] + rg[r];
  150.     int id = lower_bound(all(xs), xs[l] + xs[r]) - xs.begin() - 1;
  151.     ll cntL = cnt.get(0, id);
  152.     ll sumxL = sumx1.get(0, id);
  153.     res += sumxL - (ll)xs[l] * cntL;
  154.     ll cntR = cnt.get(id + 1, sz - 1);
  155.     ll sumxR = sumx2.get(id + 1, sz - 1);
  156.     res += (ll)xs[r] * cntR - sumxR;
  157.     return res;
  158. }
  159.  
  160. void solve(int l,int r,int from,int to){
  161.     if(l > r)
  162.         return;
  163.     int m = (l + r) >> 1;
  164.     int st = max(m, from);
  165.     ll best = longinf;
  166.     int opt = 0;
  167.     for(int i = st; i <= to; i++){
  168.         fix(m, i);
  169.         assert(L == m);
  170.         assert(R == i);
  171.         cL = cR = 0;
  172.         ll t = calc(m, i);
  173.         if(t < best){
  174.             best = t;
  175.             opt = i;
  176.         }
  177.     }
  178.     if(best < ans){
  179.         ans = best;
  180.     }
  181.     solve(m + 1, r, opt, to);
  182.     solve(l, m - 1, from, opt);
  183. }
  184.  
  185. ll solve_two(){
  186.     for(int i = 1; i <= n; i++){
  187.         if(p1[i] == p2[i])
  188.             continue;
  189.         vbegs[getid(x2[i])].push_back(ii(x1[i], i));
  190.         vends[getid(x1[i])].push_back(ii(x2[i], i));
  191.     }
  192.     int sz = xs.size();
  193.     for(int i = 0; i < sz; i++){
  194.         sort(all(vbegs[i]));
  195.         reverse(all(vbegs[i]));
  196.         sort(all(vends[i]));
  197.     }
  198.     memset(used, -1, sizeof used);
  199.     init();
  200.     solve(0, sz - 1, 0, sz - 1);
  201.     return ans;
  202. }
  203.  
  204. int main(){
  205.  
  206. #ifdef KAZAR
  207.     freopen("f.input","r",stdin);
  208.     freopen("f.output","w",stdout);
  209.     freopen("error","w",stderr);
  210. #endif
  211.  
  212.     int k = read();
  213.     n = read();
  214.  
  215.     ll more = 0;
  216.     for(int i = 1; i <= n; i++){
  217.         scanf(" %c %d %c %d", p1 + i, x1 + i, p2 + i, x2 + i);
  218.         if(x1[i] > x2[i])
  219.             swap(x1[i], x2[i]);
  220.         xs.push_back(x1[i]);
  221.         xs.push_back(x2[i]);
  222.         xs.push_back(x1[i] + x2[i]);
  223.         more += x2[i] - x1[i];
  224.         if(p1[i] != p2[i])
  225.             ++more;
  226.     }
  227.  
  228.     sort(all(xs));
  229.     xs.erase(unique(all(xs)), xs.end());
  230.  
  231.     pre();
  232.  
  233.     if(k == 1){
  234.         printf("%lld\n", solve_one() * 2 + more);
  235.         return 0;
  236.     }
  237.  
  238.     printf("%lld\n", solve_two() * 2 + more);
  239.  
  240.     return 0;
  241. }
Runtime error #stdin #stdout 0.14s 32584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/We0zDK
language:
C++ (gcc 8.3)
created:
8 years 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!