oj.uz

Submission #490580

# Submission time Handle Problem Language Result Execution time Memory
490580 2021-11-28T04:50:44 Z DeadlyCritic Palembang Bridges (APIO15_bridge) C++17
22 / 100
 187 ms 28520 KB 
#include <bits/stdc++.h>
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize("no-stack-protector,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie();

#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define uni(v) sort(all(v)), v.erase(unique(all(v)), v.end())

// #define c0 (v << 1)
// #define c1 (c0 | 1)
// #define md ((l+r)>>1)

using namespace std;

typedef long long ll;

const int maxN = 2e5+7;


int k, n, sz;
ll fix;

vector<pair<int, int>> ed;

vector<int> df;

map<int, int> mp;
int demp[maxN];

pair<int, int> pr[maxN];
vector<int> st[maxN], en[maxN];


ll dis(pair<int, int> a, ll p){
    return abs(a.fr-p)+abs(a.sc-p)+1;
}

int sumer(pair<int, int> a){
    return a.fr+a.sc;
}

int sumer(int a, int b){
    return a+b;
}

signed main(){IOS


    cin >> k >> n;
    

    for(int i = 0; i < n; i++){
        char t1, t2;
        int x1, x2;
        cin >> t1 >> x1 >> t2 >> x2;
        if(t1 == t2){
            fix += abs(x2-x1);
        }
        else{
            ed.push_back({min(x1, x2), max(x1, x2)});
            df.push_back(x1);
            df.push_back(x2);
        }
    }

    n = ed.size();

    uni(df);

    sz = df.size();

    if(sz == 1){
        cout << 0 << '\n';
        return 0;
    }

    for(int i = 0; i < sz; i++)mp[df[i]] = i, demp[i] = df[i];

    for(int i = 0; i < n; i++){
        ed[i].fr = mp[ed[i].fr];
        ed[i].sc = mp[ed[i].sc];
        pr[i] = {ed[i].fr, ed[i].sc};
        st[ed[i].fr].push_back(i);
        en[ed[i].sc].push_back(i);
    }
    
    if(k == 1){
        int po = 0;
        ll now = 0;
        int l = en[po].size(), r = n-st[po].size();

        for(int i = 0; i < n; i++){
            ll x = dis({demp[ed[i].fr], demp[ed[i].sc]}, demp[po]);
            now += x;
        }

        ll ans = now;

        while(po+1 < sz){
            ll delt = demp[po+1]-demp[po];
            now += (l*2-r*2)*delt;
            ans = min(ans, now);
            po++;
            l += en[po].size();
            r -= st[po].size();
        }

        cout << fix+ans << '\n';
        return 0;
    }

    int po = 0, qo = 0;
    ll now = 0;
    int l0 = en[po].size(), l1 = 0, r0 = 0, r1 = n-st[po].size();

    for(int i = 0; i < n; i++){
        ll x = dis({demp[ed[i].fr], demp[ed[i].sc]}, demp[po]);
        now += x;
    }

    ll ans = now;

    priority_queue<pair<int, int>> pq;

    while(po+1 < sz){
        ll delt = demp[po+1]-demp[po];
        now -= (r1-r0)*delt*2;
        ans = min(ans, now);
        po++;
        
        r1 -= st[po].size();
        r0 += en[po].size();

        for(auto i : en[po]){
            pq.push({-sumer(pr[i]), i});
        }

        while(pq.size() && -pq.top().fr <= po+qo){
            r0--;
            l1++;
            pq.pop();
        }
        

        while(qo+1 < po){
            ll delt = demp[qo+1]-demp[qo];
            ll nxt = now;
            nxt -= (l1-l0)*delt*2;

            if(nxt > now)break;

            qo++;

            while(pq.size() && -pq.top().fr <= po+qo){
                r0--;
                l1++;
                pq.pop();
            }

            for(auto i : st[qo]){
                if(pr[i].sc <= po)l1--;
            }
            
            l0 += en[qo].size();
        }
    }

    cout << fix+ans << '\n';

}

/*

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

===

24

===

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

===

22

===

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9804 KB Output is correct
6 Correct 5 ms 9760 KB Output is correct
7 Correct 5 ms 9804 KB Output is correct
8 Correct 5 ms 9804 KB Output is correct
9 Correct 6 ms 9872 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 5 ms 9804 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 7 ms 9804 KB Output is correct
5 Correct 6 ms 9804 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 6 ms 9804 KB Output is correct
8 Correct 6 ms 9804 KB Output is correct
9 Correct 8 ms 9804 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 6 ms 9804 KB Output is correct
12 Correct 31 ms 13644 KB Output is correct
13 Correct 187 ms 28520 KB Output is correct
14 Correct 77 ms 13788 KB Output is correct
15 Correct 129 ms 20724 KB Output is correct
16 Correct 36 ms 13300 KB Output is correct
17 Correct 97 ms 28468 KB Output is correct
18 Correct 105 ms 28492 KB Output is correct
19 Correct 175 ms 27912 KB Output is correct
20 Correct 39 ms 13424 KB Output is correct
21 Correct 112 ms 28500 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9628 KB Output is correct
4 Incorrect 5 ms 9676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 4 ms 9676 KB Output is correct
4 Incorrect 5 ms 9676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Incorrect 5 ms 9676 KB Output isn't correct
5 Halted 0 ms 0 KB -