제출 #712994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712994		MrKustic	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	209 ms	29200 KiB

bridge

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb emplace_back
#define x first
#define y second
#define ff first
#define ss second
 
using namespace std;
//using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pt;
typedef pair<ll, ll> ptll;
typedef complex<double> ftype;
//typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//typedef gp_hash_table<int, int> table;
 
template <typename T1, typename T2>
istream& operator>>(istream& is, pair <T1, T2>& a){
    is >> a.ff >> a.ss;
    return is;
}
 
template<typename T>
istream &operator>>(istream &in, vector<T> &list){
    for (auto &x: list)
        in >> x;
    return in;
}
 
template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair <T1, T2> a){
    os << a.ff << " " << a.ss << " ";
    return os;
}
 
template<typename T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    for (auto x : list)
        out << x << " ";
    return out;
}
 
mt19937 rnd(31);
 
void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}
 
 
//#pragma GCC optimize(3)
/*#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")*/
 
 
//-------------------------------------------
 
const int MAXN = 2e5 + 10;
 
pt poses[MAXN];
vector<int> start[MAXN], stop[MAXN];
 
ll solve1(int n){
    if (n == 0)
        return 0;
    sort(poses, poses + n, [&](pt a, pt b){return a.y < b.y;});
    ll ans = 1e18;
    vector<int> xs;
    for (int i = 0; i < n; i++){
        xs.push_back(poses[i].x);
        xs.push_back(poses[i].y);
    }
    sort(all(xs));
    xs.resize(unique(all(xs)) - xs.begin());
    ll sum1 = 0, sum2 = 0, mid = 0;
    ll cnt1 = 0, cnt2 = 0, cntmid = 0;
    map<int, int> coords;
    for (int x: xs)
        coords[x] = 0;
    int tt = 0;
    for (auto &[x, y]: coords)
        y = tt++;
    for (int i = 0; i < n; i++){
        sum2 += poses[i].x + poses[i].y;
        cnt2++;
        start[coords[poses[i].x]].push_back(i);
        stop[coords[poses[i].y]].push_back(i);
    }
    for (int i = 0; i < sz(xs); i++){
        ll pos = xs[i];
        for (int j: start[i]){
            auto [x, y] = poses[j];
            sum2 -= x + y;
            mid += abs(x - y);
            cnt2--;
            cntmid++;
        }
        for (int j: stop[i]){
            auto [x, y] = poses[j];
            mid -= abs(x - y);
            sum1 += x + y;
            cntmid--;
            cnt1++;
        }
        ans = min(ans, 2 * pos * cnt1 - sum1 + mid + sum2 - 2 * pos * cnt2);
    }
    return ans + n;
}
 
ll res[MAXN];
 
ll solve2(int n){
    if (n == 0)
        return 0;
    if (n == 1)
        return poses[0].y - poses[0].x + 1;
    sort(poses, poses + n, [&](pt a, pt b){return a.x + a.y < b.x + b.y;});
    multiset<int> l, r;
    ll sl, sr;
    sl = sr = 0;
    ll ans = 1e18;
    for (int i = 0; i < n; i++){
        auto [x1, x2] = poses[i];
        for (int x: {x1, x2}) {
            if (i == 0 || x >= *r.begin()) {
                r.insert(x);
                sr += x;
            } else {
                l.insert(x);
                sl += x;
            }
        }
        while (sz(l) < sz(r)){
            int x = *r.begin();
            r.erase(r.begin());
            sr -= x;
            l.insert(x);
            sl += x;
        }
        while (sz(l) > sz(r) + 1){
            int x = *(--l.end());
            l.erase(--l.end());
            sl -= x;
            r.insert(x);
            sr += x;
        }
        ll x = *(--l.end());
        ll curr = x * sz(l) - sl + sr - x * sz(r);
        res[i] = curr;
    }
    l.clear();
    r.clear();
    sl = sr = 0;
    for (int i = n - 1; i > 0; i--){
        auto [x1, x2] = poses[i];
        for (int x: {x1, x2}) {
            if (i == 0 || x >= *r.begin()) {
                r.insert(x);
                sr += x;
            } else {
                l.insert(x);
                sl += x;
            }
        }
        while (sz(l) < sz(r)){
            int x = *r.begin();
            r.erase(r.begin());
            sr -= x;
            l.insert(x);
            sl += x;
        }
        while (sz(l) > sz(r) + 1){
            int x = *(--l.end());
            l.erase(--l.end());
            sl -= x;
            r.insert(x);
            sr += x;
        }
        ll x = *(--l.end());
        ll curr = x * sz(l) - sl + sr - x * sz(r);
        res[i - 1] += curr;
    }
    for (int i = 0; i < n - 1; i++)
        ans = min(ans, res[i]);
    return ans + n;
}
 
void run() {
    int k, n;
    k = 2;
    n = 1e5;
    cin >> k >> n;
    ll var = 0;
    int tt = 0;
    for (int i = 0; i < n; i++){
        char c1, c2;
        int pos1, pos2;
        c1 = 'A', c2 = 'B';
        pos1 = rnd() % 1000000000, pos2 = rnd() % 1000000000;
        cin >> c1 >> pos1 >> c2 >> pos2;
        if (pos1 > pos2)
            swap(pos1, pos2);
        if (c1 == c2){
            var += abs(pos1 - pos2);
        } else {
            poses[tt++] = {pos1, pos2};
        }
    }
    n = tt;
    if (k == 1){
        cout << var + solve1(n) << '\n';
    } else {
        cout << var + solve2(n) << '\n';
    }
}
 
int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#else
    fastio();
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif
    auto start = chrono::high_resolution_clock::now();
    run();
    auto stop = chrono::high_resolution_clock::now();
#ifdef LOCAL
    cerr << "\nProgram finished in " << (ld)chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1e3 << " sec\n";
#endif
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'll solve1(int)':
bridge.cpp:88:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for (auto &[x, y]: coords)
      |                ^
bridge.cpp:99:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |             auto [x, y] = poses[j];
      |                  ^
bridge.cpp:106:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |             auto [x, y] = poses[j];
      |                  ^
bridge.cpp: In function 'll solve2(int)':
bridge.cpp:130:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |         auto [x1, x2] = poses[i];
      |              ^
bridge.cpp:162:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  162 |         auto [x1, x2] = poses[i];
      |              ^
bridge.cpp: In function 'int main()':
bridge.cpp:232:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  232 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
bridge.cpp:234:10: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
  234 |     auto stop = chrono::high_resolution_clock::now();
      |          ^~~~

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