fork(1) download
  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
stdin
Standard input is empty
stdout
Standard output is empty