Submission #46039

#	Time	Username	Problem	Language	Result	Execution time	Memory
46039		mirbek01	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	2056 ms	78868 KiB

bridge

# include <bits/stdc++.h>
#pragma GCC optimize("Ofast")


# define f first
# define s second

using namespace std;

const int N = 1e5 + 2;

struct st{
      int cnt, l, r;
      long long sum = 0;
      st(){
            cnt = sum = l = r = 0;
      }
}t[N * 30];

int n, k, cn, sz = 1, root[N];
long long ans = 1e18, p1[N], s1[N], p2[N], s2[N], ss;
vector <int> v, v1, v2;
pair < pair <int, int> , pair <char, char> > a[N];
pair <int, pair <int, int> > b[N];

void update(int ov, int nv, int pos, int tl = 0, int tr = 1e9){
      if(tl == tr){
            t[nv].cnt = t[ov].cnt + 1;
            t[nv].sum = t[ov].sum + tl;
      } else {
            int tm = (tl + tr) >> 1;
            if(pos <= tm){
                  if(!t[nv].l) t[nv].l = ++ sz;
                  t[nv].r = t[ov].r;
                  update(t[ov].l, t[nv].l, pos, tl, tm);
            } else {
                  if(!t[nv].r) t[nv].r = ++ sz;
                  t[nv].l = t[ov].l;
                  update(t[ov].r, t[nv].r, pos, tm + 1, tr);
            }
            t[nv].sum = t[ t[nv].l ].sum + t[ t[nv].r ].sum;
            t[nv].cnt = t[ t[nv].l ].cnt + t[ t[nv].r ].cnt;
      }
}

pair <long long, int> get(int ov, int nv, int l, int r, int tl = 0, int tr = 1e9){
      if(t[nv].cnt - t[ov].cnt <= 0) return {0, 0};
      if(l <= tl && tr <= r) return {t[nv].sum - t[ov].sum, t[nv].cnt - t[ov].cnt};
      int tm = (tl + tr) >> 1;
      pair <long long, int> res, cp;
      if(l <= tm) res = get(t[ov].l, t[nv].l, l, r, tl, tm);
      if(tm < r){
            cp = get(t[ov].r, t[nv].r, l, r, tm + 1, tr);
            res.f += cp.f;
            res.s += cp.s;
      }
      return res;
}

int main(){
      ios_base::sync_with_stdio(0);
      cin.tie(0);

      cin >> k >> n;

      for(int i = 1; i <= n; i ++){
            cin >> a[i].s.f >> a[i].f.f >> a[i].s.s >> a[i].f.s;
            if(a[i].f.f > a[i].f.s) swap(a[i].f.f, a[i].f.s);
            if(a[i].s.f != a[i].s.s) {
                  cn ++;
                  v1.push_back(a[i].f.f), v2.push_back(a[i].f.s);
                  b[cn] = {(a[i].f.f + a[i].f.s + 1), {a[i].f.f, a[i].f.s}};
            } else {
                  ss += abs(a[i].f.s - a[i].f.f);
            }
            v.push_back(a[i].f.f);
            v.push_back(a[i].f.s);
      }

      v1.push_back(-1e9);
      v2.push_back(-1e9);

      sort(b + 1, b + cn + 1);
      sort(v.begin(), v.end());
      v.resize(unique(v.begin(), v.end()) - v.begin());
      sort(v1.begin(), v1.end());
      sort(v2.begin(), v2.end());

      for(int i = 1; i <= cn; i ++){
            p1[i] = p1[i - 1] + v1[i];
            p2[i] = p2[i - 1] + v2[i];
      }
      for(int i = cn; i >= 1; i --){
            s1[i] = s1[i + 1] + v1[i];
            s2[i] = s2[i + 1] + v2[i];
      }

      int pos = 0, ps = 0;

      for(int i = 0; i < v.size(); i ++){
            long long res = 0;
            int x = v[i];
            while(pos + 1 <= cn && v1[pos + 1] <= x) pos ++;
            while(ps + 1 <= cn && v2[ps + 1] <= x) ps ++;
            res += x * 1ll * pos - p1[pos];
            res += x * 1ll * ps - p2[ps];
            res += s1[pos + 1] - x * 1ll * (cn - pos);
            res += s2[ps + 1] - x * 1ll * (cn - ps);
            ans = min(ans, res + cn + ss);
      }

      if(k == 2){
            long long mn = 1e18;
            for(int i = 1; i <= cn; i ++){
                  root[i * 2 - 1] = ++ sz;
                  update(root[i * 2 - 2], root[i * 2 - 1], b[i].s.f);
                  root[i * 2] = ++ sz;
                  update(root[i * 2 - 1], root[i * 2], b[i].s.s);
            }
            for(int i = 0; i < v.size(); i ++){
                  ps = 0;
                  long long sum1 = 0, sum2 = 0;
                  int cnt1 = 0, cnt2 = 0;
                  for(int j = i + 1; j < v.size(); j ++){
                        long long res = 0;
                        int x = (v[i] + v[j] + 1);
                        while(b[ps + 1].f <= x && ps + 1 <= cn) {
                              ps ++;
                              if(b[ps].s.f <= v[i]) sum1 += b[ps].s.f, cnt1 ++;
                              else sum2 += b[ps].s.f, cnt2 ++;
                              if(b[ps].s.s <= v[i]) sum1 += b[ps].s.s, cnt1 ++;
                              else sum2 += b[ps].s.s, cnt2 ++;
                        }
                        res += v[i] * 1ll * cnt1 - sum1;
                        res += sum2 - v[i] * 1ll * cnt2;
                        pair <long long, int> p = get(root[ps * 2], root[cn * 2], 0, v[j]);
                        res += v[j] * 1ll * p.s - p.f;
                        p = get(root[ps * 2], root[cn * 2], v[j] + 1, 1e9);
                        res += p.f - v[j] * 1ll * p.s;
                        if(mn > res) mn = res;
                  }
            }
            ans = min(ans, mn + cn + ss);
      }

      cout << ans;
//      cin.get(); cin.get();
}
/***
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
***/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:100:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < v.size(); i ++){
                      ~~^~~~~~~~~~
bridge.cpp:120:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v.size(); i ++){
                            ~~^~~~~~~~~~
bridge.cpp:124:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = i + 1; j < v.size(); j ++){
                                      ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37