oj.uz

Submission #249772

# Submission time Handle Problem Language Result Execution time Memory
249772 2020-07-15T17:17:51 Z rdd6584 Palembang Bridges (APIO15_bridge) C++14
100 / 100
 680 ms 23788 KB 
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const ll MOD = (ll)1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

ll fac[1] = {1}, inv[1] = {1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll mp(ll a,ll b){ll ret=1;while(b){if(b&1)ret=ret*a%MOD;a=a*a%MOD;b>>=1;}return ret;}
ll cmb(ll r, ll c) {return fac[r] * inv[c] % MOD * inv[r - c] % MOD;}

vector<pll> v;
vector<int> cc;

ll cal(int mid) {
    ll ret= 0;
    for (pll i : v) {
        if (i.first <= mid && mid <= i.second) ret += (i.second-i.first);
        else ret += abs(i.first-mid) + abs(i.second-mid);
    }
    return ret;
}

int n;
vector<ll> x;
int szz = 200000;

struct pen {
    ll tree[200001];
    void upd(int i, ll val) {
        for (; i <= szz; i+=i&-i) tree[i]+=val;
    }
    ll find(int i) {
        ll ret = 0;
        for (; i; i-= i&-i) ret += tree[i];
        return ret;
    }
} lsum, lro, rsum, rro;

ll lp[100001];
ll rp[100001];

ll gg(ll mid) {
    int t = lower_bound(all(x), mid) - x.begin();
    ll ret = 0;
    ret += lro.find(t)*mid - lsum.find(t);
   //  printf("/// %lld : %lld\n", mid, ret );

    ret += (rsum.find(200000) - rsum.find(t)) - (rro.find(200000) - rro.find(t))*mid;

   //  printf("/// %lld : %lld\n", mid, ret );

    ret += rro.find(t)*mid - rsum.find(t);
    ret += (lsum.find(200000) - lsum.find(t)) - (lro.find(200000) - lro.find(t))*mid;
   //  printf("/// %lld : %lld\n", mid, ret );

    return ret;
}

int main() {
    int k;
    scanf("%d %d", &k, &n);

    ll sum = 0;
    for (int i = 0; i < n; i++) {
        char a,c;
        int b,d;
        scanf(" %c %d %c %d", &a, &b ,&c, &d);
        if (a!=c) {
            if (b>d) swap(b,d);
            sum++;
            v.push_back({b, d});
            x.push_back(b);
            x.push_back(d);
        }
        else sum += abs(b-d);
    }
    x.push_back(-1);
    sort(all(x));
    x.erase(unique(all(x)), x.end());

    for (pll i : v) cc.push_back(i.first), cc.push_back(i.second);
    sort(all(cc));

    if (k==1) {
        if (cc.empty()) printf("%lld\n", sum);
        else printf("%lld", cal(cc[sz(cc)/2])+sum);
        return 0;
    }


    sort(all(v), [](pll a, pll b){return a.first+a.second < b.first+b.second;});

    multiset<ll> se;
    auto med = se.begin();
    for (int cnt = 0; cnt < 2; cnt++) {
        se.clear();
        if (cnt==1) {
            memcpy(rp, lp, sizeof(lp));
            reverse(all(v));
            memset(lsum.tree, 0, sizeof(ll)*(szz+1));
            memset(rsum.tree, 0, sizeof(ll)*(szz+1));

            memset(lro.tree, 0, sizeof(ll)*(szz+1));
            memset(rro.tree, 0, sizeof(ll)*(szz+1));
        }

        for (int i = 0; i < sz(v); i++) {
            int lt = lower_bound(all(x), v[i].first) - x.begin();
            lsum.upd(lt, v[i].first);
            lro.upd(lt, 1);

            int rt = lower_bound(all(x), v[i].second) - x.begin();
            rsum.upd(rt, v[i].second);
            rro.upd(rt, 1);


            if (se.empty()) se.insert(v[i].first), med = se.begin();
            else {
                se.insert(v[i].first);
                if (sz(se) % 2 && *med < v[i].first) med++;
                else if (sz(se) % 2 == 0 && *med >= v[i].first) med--;
            }

            se.insert(v[i].second);
            if (sz(se) % 2 && *med < v[i].second) med++;
            else if (sz(se) % 2 == 0 && *med >= v[i].second) med--;


            int le = 0, ri = sz(x) - 1, mid;
            while (le<=ri) {
                mid = (le+ri)/2;
                int t = lro.find(mid) + rro.find(mid);
                if (t >= i+1) ri = mid - 1;
                else le = mid + 1;
            }

            // assert(x[le] == *med);
            // printf("%lld %lld\n", x[le], *med);
            lp[i] = gg(x[le]);
            // printf("%d : %lld %lld / %lld %lld \n", i, v[i].first, v[i].second, lp[i], *med);
        }
    }

    ll ans = 9e18;
    for (int i = 0; i < sz(v) - 1; i++) {
        ans = min(ans, lp[i] + rp[sz(v) - i - 2]);
        // printf("%d : %d : %lld %lld\n", sz(v) - i - 2, i, rp[sz(v)-i-2], lp[i]);
    }

    if (ans > 5e18 && sz(cc)) printf("%lld", cal(cc[sz(cc)/2])+sum);
    else if (ans > 5e18) printf("%lld", sum);
    else printf("%lld", sum+ans);
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &k, &n);
     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %c %d", &a, &b ,&c, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 42 ms 6104 KB Output is correct
13 Correct 87 ms 7512 KB Output is correct
14 Correct 65 ms 6104 KB Output is correct
15 Correct 51 ms 4452 KB Output is correct
16 Correct 47 ms 6872 KB Output is correct
17 Correct 68 ms 7504 KB Output is correct
18 Correct 74 ms 7128 KB Output is correct
19 Correct 88 ms 7512 KB Output is correct
20 Correct 52 ms 7128 KB Output is correct
21 Correct 74 ms 7256 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7296 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 5 ms 7424 KB Output is correct
7 Correct 5 ms 7424 KB Output is correct
8 Correct 5 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 5 ms 7424 KB Output is correct
12 Correct 5 ms 7424 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 5 ms 7424 KB Output is correct
7 Correct 5 ms 7424 KB Output is correct
8 Correct 5 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 5 ms 7424 KB Output is correct
12 Correct 5 ms 7424 KB Output is correct
13 Correct 6 ms 7552 KB Output is correct
14 Correct 6 ms 7552 KB Output is correct
15 Correct 7 ms 7552 KB Output is correct
16 Correct 5 ms 7424 KB Output is correct
17 Correct 6 ms 7424 KB Output is correct
18 Correct 5 ms 7424 KB Output is correct
19 Correct 6 ms 7552 KB Output is correct
20 Correct 7 ms 7552 KB Output is correct
21 Correct 6 ms 7552 KB Output is correct
22 Correct 7 ms 7552 KB Output is correct
23 Correct 6 ms 7552 KB Output is correct
24 Correct 7 ms 7552 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7424 KB Output is correct
2 Correct 4 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 4 ms 7424 KB Output is correct
7 Correct 5 ms 7424 KB Output is correct
8 Correct 5 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 6 ms 7424 KB Output is correct
11 Correct 5 ms 7424 KB Output is correct
12 Correct 5 ms 7424 KB Output is correct
13 Correct 6 ms 7552 KB Output is correct
14 Correct 6 ms 7552 KB Output is correct
15 Correct 7 ms 7552 KB Output is correct
16 Correct 5 ms 7424 KB Output is correct
17 Correct 6 ms 7424 KB Output is correct
18 Correct 8 ms 7424 KB Output is correct
19 Correct 6 ms 7552 KB Output is correct
20 Correct 7 ms 7552 KB Output is correct
21 Correct 7 ms 7552 KB Output is correct
22 Correct 10 ms 7544 KB Output is correct
23 Correct 8 ms 7552 KB Output is correct
24 Correct 7 ms 7552 KB Output is correct
25 Correct 202 ms 22224 KB Output is correct
26 Correct 282 ms 22488 KB Output is correct
27 Correct 613 ms 23376 KB Output is correct
28 Correct 665 ms 23788 KB Output is correct
29 Correct 680 ms 23772 KB Output is correct
30 Correct 254 ms 16228 KB Output is correct
31 Correct 190 ms 23132 KB Output is correct
32 Correct 315 ms 23760 KB Output is correct
33 Correct 296 ms 23520 KB Output is correct
34 Correct 341 ms 23764 KB Output is correct
35 Correct 181 ms 23508 KB Output is correct
36 Correct 322 ms 23512 KB Output is correct
37 Correct 173 ms 22300 KB Output is correct