oj.uz

Submission #490576

# Submission time Handle Problem Language Result Execution time Memory
490576 2021-11-28T04:15:37 Z DeadlyCritic Palembang Bridges (APIO15_bridge) C++17
22 / 100
 192 ms 30704 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;
}


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();

    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);
    }
    
    assert(k == 1);

    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;
    }

}

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9592 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 9804 KB Output is correct
5 Correct 5 ms 9804 KB Output is correct
6 Correct 5 ms 9676 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 9804 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 5 ms 9884 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 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 6 ms 9804 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 6 ms 9804 KB Output is correct
12 Correct 28 ms 13616 KB Output is correct
13 Correct 192 ms 28480 KB Output is correct
14 Correct 66 ms 14992 KB Output is correct
15 Correct 103 ms 22112 KB Output is correct
16 Correct 38 ms 14972 KB Output is correct
17 Correct 99 ms 30704 KB Output is correct
18 Correct 103 ms 30412 KB Output is correct
19 Correct 169 ms 30332 KB Output is correct
20 Correct 38 ms 15284 KB Output is correct
21 Correct 113 ms 30544 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 19532 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 19488 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 19532 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -