oj.uz

Submission #1112645

# Submission time Handle Problem Language Result Execution time Memory
1112645 2024-11-14T13:28:41 Z fryingduc Palembang Bridges (APIO15_bridge) C++17
100 / 100
 223 ms 21516 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long

#define left oawenopigeawg
#define right awhopegiheoag

const int maxn = 2e5 + 5;
const int inf = 1e18;
int n, k;

struct interval { 
    int x, op, id;
    bool operator<(const interval &o) {
        return x < o.x;
    }
};
pair<int, int> a[maxn];

namespace sub12 {
    void solve() {
        int ans = inf;
        int sum = 0;
        vector<interval> sweep;
        int sz = 0;
        for(int i = 1; i <= n; ++i) {
            int l, r;
            char x, y;
            cin >> x >> l >> y >> r;
            if(l > r) swap(l, r);
            if(x == y) {
                sum += (r - l);
            }
            else {
                ++sz;
                sweep.push_back({l, 1, sz});
                sweep.push_back({r, -1, sz});
                
                a[sz] = {l, r};
            }
        }
        n = sz;
        sort(sweep.begin(), sweep.end());
        set<int> s;
        int others = 0;
        int nxt = 0, cur_sum = 0;
        for(int i = 1; i <= n; ++i) {
            nxt += (a[i].first + a[i].second);
        }
        ans = nxt;
        int pref = 0, suf = n;
        for(int i = 0; i < (int)sweep.size(); ++i) {
            int cur = 0;
            while(i + cur < (int)sweep.size() and sweep[i].x == sweep[i + cur].x) {
                int op = sweep[i + cur].op, id = sweep[i + cur].id;
                if(op == 1) {
                    s.insert(id);
                    cur_sum += (a[id].second - a[id].first);
                    nxt -= (a[id].first + a[id].second);
                    --suf;
                }
                else { 
                    others += (a[id].first + a[id].second);
                    s.erase(id);
                    cur_sum -= (a[id].second - a[id].first);
                    ++pref;
                }
                int x = sweep[i].x;    
                int res = cur_sum + (2 * pref * x - others) + (nxt - 2 * x * suf);
    //            cerr << i + cur << " " << s.size() << " " << pref << " " << suf << " " << others << " " << nxt << " " << res << '\n';
                ++cur;
            }
            int x = sweep[i].x;
            int res = cur_sum + (2 * pref * x - others) + (nxt - 2 * x * suf);
            ans = min(ans, res);
            i = i + cur - 1;
        }
        cout << ans + sum + sz;   
    }
}
namespace sub34 {
    multiset<int> left, right;
    int left_sum, right_sum;
    void adjust() {
        while((int)left.size() and right.size()) {
            if(*(--left.end()) <= *(right.begin())) {
                break;
            }
            int it = *(--left.end());
            left_sum -= it;
            left.erase(left.find(it));
            right.insert(it);
            right_sum += it;
        }
        while((int)left.size() - (int)right.size() > 1) {
            int it = *(--left.end());
            left.erase(left.find(it));
            left_sum -= it;
            right_sum += it;
            right.insert(it);
        }
        while((int)right.size() - (int)left.size() > 0) {
            int it = *(right.begin());
            right.erase(right.find(it));
            right_sum -= it;
            left_sum += it;
            left.insert(it);
        }
    }
    void erase(int x) {
        if(left.find(x) != left.end()) {
            left.erase(left.find(x));
            left_sum -= x;
        }
        else if(right.find(x) != right.end()) {
            right.erase(right.find(x));
            right_sum -= x;
        }
        adjust();
    }
    void solve() {
        int ans = inf;
        vector<int> vec;
        int sum = 0;
        vector<interval> sweep;
        int sz = 0;
        for(int i = 1; i <= n; ++i) {
            int l, r;
            char x, y;
            cin >> x >> l >> y >> r;
            if(l > r) swap(l, r);
            if(x == y) {
                sum += (r - l);
            }
            else {
                ++sz;
                sweep.push_back({l, 1, sz});
                sweep.push_back({r, -1, sz});
                
                vec.push_back(l);
                vec.push_back(r);
                
                a[sz] = {l, r};
            }
        }
        n = sz;
        sort(sweep.begin(), sweep.end());
        sort(vec.begin(), vec.end());
        sort(a + 1, a + n + 1, [](const pair<int, int> &x, const pair<int, int> &y) -> bool {
            return x.first + x.second < y.first + y.second;
        });
        vector<int> pref(sz + 1), suf(sz + 1);
        for(int i = 1; i <= n; ++i) {
            left.insert(a[i].first);
            left.insert(a[i].second);
            left_sum += a[i].first;
            left_sum += a[i].second;
            adjust();
            
            pref[i] = inf;
            if(left.size()) {
                int cur_med = *(--left.end());
                pref[i] = (cur_med * (left.size()) - left_sum) + (right_sum - cur_med * (right.size()));
//                cerr << i << " " << left_sum << " " << right_sum << " " << cur_med << " " << pref[i] << '\n';
//                for(auto i:right) cerr << i << " ";
//                cerr << '\n';
            }
        }
        left.clear();
        right.clear();
        left_sum = right_sum = 0;
        cerr << '\n';
        for(int i = n; i; --i) {
            left.insert(a[i].first);
            left.insert(a[i].second);
            left_sum += a[i].first;
            left_sum += a[i].second;
            adjust();
            
            if(left.size()) {
                int cur_med = *(--left.end());
                
                suf[i] = (cur_med * (left.size()) - left_sum) + (right_sum - cur_med * (right.size()));
//                cerr << i << " " << left_sum << " " << right_sum << " " << cur_med << " " << suf[i] << '\n';
            }
        }
        
        for(int i = 0; i <= n; ++i) {
            ans = min(ans, pref[i] + suf[i + 1]);
//            cerr << i << " " << pref[i] << " " << suf[i + 1] << '\n';
        }
        cout << ans + sz + sum;
    }
}
void solve() {
    cin >> k >> n;
    if(k == 1) {    
        sub12::solve();
        return;
    }
    if(k == 2) {
        sub34::solve();
        return;
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

Compilation message

bridge.cpp: In function 'void sub12::solve()':
bridge.cpp:70:21: warning: unused variable 'res' [-Wunused-variable]
   70 |                 int res = cur_sum + (2 * pref * x - others) + (nxt - 2 * x * suf);
      |                     ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 42 ms 10420 KB Output is correct
13 Correct 92 ms 11176 KB Output is correct
14 Correct 68 ms 9240 KB Output is correct
15 Correct 49 ms 6840 KB Output is correct
16 Correct 45 ms 12980 KB Output is correct
17 Correct 35 ms 9436 KB Output is correct
18 Correct 72 ms 13332 KB Output is correct
19 Correct 51 ms 9384 KB Output is correct
20 Correct 46 ms 11696 KB Output is correct
21 Correct 40 ms 9116 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 3 ms 592 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 2 ms 592 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 592 KB Output is correct
22 Correct 2 ms 592 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Correct 3 ms 592 KB Output is correct
25 Correct 160 ms 19832 KB Output is correct
26 Correct 189 ms 20332 KB Output is correct
27 Correct 215 ms 20976 KB Output is correct
28 Correct 223 ms 21480 KB Output is correct
29 Correct 219 ms 21516 KB Output is correct
30 Correct 101 ms 11512 KB Output is correct
31 Correct 146 ms 20712 KB Output is correct
32 Correct 180 ms 21344 KB Output is correct
33 Correct 104 ms 20968 KB Output is correct
34 Correct 185 ms 21400 KB Output is correct
35 Correct 163 ms 21040 KB Output is correct
36 Correct 206 ms 21232 KB Output is correct
37 Correct 121 ms 19956 KB Output is correct