Submission #585590

#	Time	Username	Problem	Language	Result	Execution time	Memory
585590		tamthegod	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	476 ms	62284 KiB

bridge

#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int k, n;
int res = 0;
int m = 0;
vector<int> vc;
map<int, int> mp;
struct TCitizen
{
    char p;
    int s;
    char q;
    int t;
} a[maxN];
map<int, int> nerf, origin;
void ReadInput()
{
    cin >> k >> n;
    for(int i=1; i<=n; i++)
    {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
        vc.pb((s + t) / 2);
        if(p == q)
        {
            res += abs(s - t);
            continue;
        }
        vc.pb(s);
        vc.pb(t);
        if(s > t)
            swap(s, t);
        a[++m] = {p, s, q, t};
    }
    vector<int> vc;
    for(int i=1; i<=m; i++)
    {
        vc.pb(a[i].s);
        vc.pb(a[i].t);
        vc.pb((a[i].s + a[i].t) / 2);
    }
    sort(vc.begin(), vc.end());
    int p = 0;
    for(int v : vc)
    {
        if(nerf[v]) continue;
        nerf[v] = ++p;
        origin[p] = v;
    }
}
struct BIT
{
    int n;
    vector<int> bit;
    BIT(int _n)
    {
        n = _n * 3;
        bit.resize(n + 1);
    }
    void reset()
    {
        for(int i=1; i<=n; i++) bit[i] = 0;
    }
    void update(int pos, int val)
    {
        for(; pos <= n; pos += (pos & (-pos)))
            bit[pos] += val;
    }
    int get(int pos)
    {
        int res = 0;
        for(; pos; pos -= (pos & (-pos)))
            res += bit[pos];
        return res;
    }
};
pair<int, int> bit[maxN];
void update(int pos, int val)
{
    while(pos <= n * 3)
    {
        bit[pos].fi += val;
        bit[pos].se++;
        pos += (pos & (-pos));
    }
}
pair<int, int> get(int pos)
{
    pair<int, int> res;
    while(pos)
    {
        res.fi += bit[pos].fi;
        res.se += bit[pos].se;
        pos -= (pos & (-pos));
    }
    return res;
}
pair<int, int> get_range(int l, int r)
{
    pair<int, int> val1 = get(r), val2 = get(l - 1);
    return {val1.fi - val2.fi, val1.se - val2.se};
}
void sub1()
{
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());
    sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
    {
        return p.s < q.s;
    });
    int p = 1;
    int sum = 0;
    for(int x : vc)
    {
        while(p <= m && a[p].s <= x)
        {
            sum += a[p].s;
            p++;
        }
        mp[x] += x * (p - 1) - sum;
    }
    sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
    {
        return p.t < q.t;
    });
    p = 1;
    sum = 0;
    for(int x : vc)
    {
        while(p <= m && a[p].t <= x)
        {
            sum += a[p].t;
            p++;
        }
        mp[x] += x * (p - 1) - sum;
    }
    reverse(vc.begin(), vc.end());
    sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
    {
        return p.s > q.s;
    });
    p = 1;
    sum = 0;
    for(int x : vc)
    {
        while(p <= m && a[p].s >= x)
        {
            sum += a[p].s;
            p++;
        }
        mp[x] += -(x * (p - 1) - sum);
    }
    sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
    {
        return p.t > q.t;
    });
    p = 1;
    sum = 0;
    for(int x : vc)
    {
        while(p <= m && a[p].t >= x)
        {
            sum += a[p].t;
            p++;
        }
        mp[x] += -(x * (p - 1) - sum);
    }
    int _min = oo;
    for(pair<int, int> v : mp)
        _min = min(_min, v.se);
    _min += m;
    cout << res + _min;
}
pair<int, int> ans[maxN];
void sub2()
{
    //cout << nerf[2];return;
    BIT bit1(n), bit2(n);
    sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
    {
        return p.s + p.t < q.s + q.t;
    });
    for(int i=1; i<=m; i++)
    {
        bit1.update(nerf[(a[i].s + a[i].t) / 2], 1);
        int low = 1, high = n * 3, mid;
        while(low <= high)
        {
            mid = (low + high) / 2;
            int val = bit1.get(mid);
            if(val >= (i + 1) / 2) high = mid - 1;
            else low = mid + 1;
        }
        update(nerf[a[i].s], a[i].s);
        update(nerf[a[i].t], a[i].t);
        //cout << get_range(3, 3).fi;return;
        pair<int, int> val1 = get_range(1, mid);
        ans[i].fi += origin[mid] * val1.se - val1.fi;
        pair<int, int> val2 = get_range(mid, n * 3);
        ans[i].fi += val2.fi - origin[mid] * val2.se;
        //cout << ans[i].fi << " ";
    }
  ///  return;
    memset(bit, 0, sizeof bit);
    bit1.reset();
    for(int i=m; i>=1; i--)
    {
        bit1.update(nerf[(a[i].s + a[i].t) / 2], 1);
        int low = 1, high = n * 3, mid;
     //   cout << bit1.get(15);return;
        while(low <= high)
        {
            mid = (low + high) / 2;
            int val = bit1.get(mid);
            if(val >= ((m - i + 1) + 1) / 2) high = mid - 1;
            else low = mid + 1;
        }
       // cout << origin[mid];return;
        update(nerf[a[i].s], a[i].s);
        update(nerf[a[i].t], a[i].t);
        pair<int, int> val1 = get_range(1, mid);
        ans[i].se += origin[mid] * val1.se - val1.fi;
        pair<int, int> val2 = get_range(mid, n * 3);
        ans[i].se += val2.fi - origin[mid] * val2.se;
       // cout << ans[i].se << " ";
    }
   // return;
    int _min = oo;
    for(int i=0; i<=m; i++)
    {
        _min = min(_min, ans[i].fi + ans[i + 1].se);
    }
    cout << res + m + _min;
}
void Solve()
{
    //cout << res;return;
    if(!m)
    {
        cout << res;
        return;
    }
    if(k == 1)
    {
        sub1();
    }
    else
        sub2();

}
int32_t main()
{
      //freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Compilation message (stderr)

bridge.cpp: In function 'void sub2()':
bridge.cpp:217:30: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
  217 |     memset(bit, 0, sizeof bit);
      |                              ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from bridge.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

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