fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <cstring>
  6. #include <set>
  7. #include <map>
  8. #include <cstdio>
  9.  
  10. #define pii pair<int, int>
  11. #define mp make_pair
  12. //#define pp pair<int,int>
  13. #define maxn 1050000
  14. #define ll long long
  15. #define INF 2e9
  16. #define LINF 2e14
  17. #define MOD 1000000007
  18. #define mem(a,v) memset(a,v,sizeof(a))
  19. #define rep(i,a,b) for(int i=(a);i<=(b);i++)
  20. #define pb push_back
  21. using namespace std;
  22.  
  23. int n, k, pt[100010];
  24. vector<ll> v[100010], v2;
  25. set<pii> pq;
  26. map<ll, ll> lt, gt;
  27. ll ltt, gtt;
  28. int ltcnt, gtcnt;
  29.  
  30.  
  31. int main()
  32. {
  33.     while(~scanf("%d%d", &k, &n)){
  34.         ll res = LINF;
  35.         int best;
  36.         for(int i = 0; i < 100010; i++)
  37.             v[i].clear();
  38.         memset(pt, 0, sizeof(pt));
  39.         pq.clear();
  40.         gt.clear(), gt.clear();
  41.         ltt = gtt = ltcnt = gtcnt = 0;
  42.         v2.clear();
  43.         for(int i = 0; i < n; i++){
  44.             int pos, t;
  45.             scanf("%d%d", &pos, &t);
  46.             v[--t].pb(pos);
  47.             v2.pb(pos);
  48.         }
  49.         for(int i = 0; i < k; i++){
  50.             v[i].pb(INF);
  51.             ll mid = (v[i][1]+v[i][0])/2;
  52.             pq.insert(mp(mid, i));
  53.             gt[v[i][0]] ++;
  54.             gtt += v[i][0];
  55.         }
  56.         gtcnt = k;
  57.         for(int i = 0; i < n; i++){
  58.             ll pos = v2[i];
  59.             while(gt.begin()->first < pos){
  60.                 gtt -= gt.begin()->first*gt.begin()->second;
  61.                 gtcnt -= gt.begin()->second;
  62.                 ltt += gt.begin()->first*gt.begin()->second;
  63.                 ltcnt += gt.begin()->second;
  64.                 lt[gt.begin()->first] += gt.begin()->second;
  65.                 gt.erase(gt.begin());
  66.             }
  67.             while(pq.begin()->first <= pos){
  68.                 int type = pq.begin()->second;
  69.                 pq.erase(pq.begin());
  70.                 if(pt[type] < pos){
  71.                     ltcnt--, ltt -= pt[type];
  72.                     if(--lt[pt[type]] == 0)
  73.                         lt.erase(pt[type]);
  74.                     pt[type]++;
  75.                 }
  76.                 else{
  77.                     gtcnt--, gtt-=pt[type];
  78.                     if(--gt[pt[type]] == 0)
  79.                         gt.erase(pt[type]);
  80.                     pt[type]++;
  81.                 }
  82.                 if(pt[type] < pos){
  83.                     ltcnt++, ltt += pt[type];
  84.                     lt[pt[type]]++;
  85.                 }
  86.                 else{
  87.                     gtcnt++, gtt+=pt[type];
  88.                     ++gt[pt[type]];
  89.                 }
  90.                 ll mid = (v[type][pt[type]] + v[type][pt[type]+1])/2;
  91.                 pq.insert(mp(mid, type));
  92.             }
  93.             if(res > pos*(ltcnt-gtcnt)-ltt+gtt)
  94.                 res = pos*(ltcnt-gtcnt)-ltt+gtt, best = pos;
  95.         }
  96.         printf("%d\n", best);
  97.     }
  98.     return 0;
  99. }
  100.  
Success #stdin #stdout 0.01s 6320KB
comments (?)
stdin
copy 
1 5
-100 1
-10 1
0 1
1 1
2 1
5 5
-2 1
0 3
-1 2
1 4
2 5
3 6
0 1
6 2
7 3
0 2
1 3
5 1
stdout
copy 
-100
0
0
https://ideone.com/5eaR6Z
language:
C++ (gcc 8.3)
created:
3 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!