oj.uz

Submission #685241

# Submission time Handle Problem Language Result Execution time Memory
685241 2023-01-23T17:53:44 Z omikron123 Palembang Bridges (APIO15_bridge) C++14
100 / 100
 375 ms 13688 KB 
// https://oj.uz/problem/view/APIO15_bridge

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

// K=1,2, N=1e5, 需要O(nlogn)
// 1. 家和办公室在同一边的是不参与计算的，和桥没有关系。
// 2. 最小值都在event点上面取得，而且是一个U型的阶梯函数，所以应该可以固定一个桥的位置，然后binary search另外一个。
// 3. 进一步可以发现K=1的时候，答案就是S[i], T[i]的median. 
// 4. K=2的时候，简单做法是可以暴力搜索O(n^3)，这样可以得到31分。
// 5. 正解：把|s-x|+|t-x|画出来，就可以看到，是U型左右对称，所以有两个桥的时候，应该走的是离
//    (s+t)/2近的桥。所以可以按(s+t)/2排序，分成两段后分别求median。这里可以用sliding median
//    的方法（两个multiset求siding median），O(nlogn).

// 收获：解题需要画图和抽象成公式，需要在纸上抠细节，就能找到正确解法。

int n, K;
ll ans;
vector<pair<int,int>> x;

// sliding median with 2 multisets
struct median {
    multiset<int> l, r;     // l is smaller part. size(l) >= size(r)
    ll lsum, rsum;
    median() {
        lsum = 0; rsum = 0;
    }
    void balance() {
        while (l.size() > r.size() + 1) {
            int x = *prev(l.end());
            r.insert(x);
            l.erase(l.find(x));
            rsum += x, lsum -= x;
        }
        while (r.size() > l.size()) {
            int x = *r.begin();
            l.insert(x);
            r.erase(r.find(x));
            lsum += x, rsum -= x;
        }
    }
    void add(int x) {
        if (l.empty()) {
            l.insert(x);
            lsum = x;
            return;
        }
        if (x > get()) {
            r.insert(x);
            rsum += x;
        } else {
            l.insert(x);
            lsum += x;
        }
        balance();
    }
    int get() {
        return l.empty() ? -1 : *prev(l.end());
    }
    void del(int x) {
        if (x > get())
            r.erase(r.find(x)), rsum -= x;
        else
            l.erase(l.find(x)), lsum -= x;
        balance();
    }
};

int main() {
    scanf("%d %d", &K, &n);
    for (int i = 0; i < n; i++) {
        char c1[10], c2[10];
        int x1, x2;
        scanf("%s %d %s %d", c1, &x1, c2, &x2);
        if (c1[0] == c2[0]) ans += abs(x1-x2);
        else x.push_back({min(x1,x2), max(x1,x2)});
    }

    vector<int> X;
    for (auto p: x) {
        X.push_back(p.first);
        X.push_back(p.second);
    }
    sort(X.begin(), X.end());
    if (K == 1 && x.size()) {
        // just return the median of all numbers
        int m = X[X.size() / 2];
        for (auto p: x)
            ans += abs(p.first-m) + abs(p.second-m) + 1;
    } else if (K==2 && x.size()) {
        // 正解
        median l, r;    // l is smaller
        // sort x by (s+t)/2
        sort(x.begin(), x.end(), [](pi a, pi b) {
            return (a.first+a.second) < (b.first+b.second);
        });
        // initially everything in 'r'
        ll sum = 0;
        for (int p: X)
            r.add(p);
        int mr = r.get();
        ll ans2 = r.rsum - r.lsum + x.size();

        // move pairs one by one from r to l
        for (pi p: x) {
            l.add(p.first), l.add(p.second);
            r.del(p.first), r.del(p.second);
            ll sum = l.rsum - l.lsum + r.rsum - r.lsum + x.size();
            ans2 = min(ans2, sum);
        }
        ans += ans2;
    }

    printf("%lld", ans);

    return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:106:12: warning: unused variable 'sum' [-Wunused-variable]
  106 |         ll sum = 0;
      |            ^~~
bridge.cpp:109:13: warning: unused variable 'mr' [-Wunused-variable]
  109 |         int mr = r.get();
      |             ^~
bridge.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d %d", &K, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%s %d %s %d", c1, &x1, c2, &x2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 30 ms 3100 KB Output is correct
13 Correct 46 ms 3080 KB Output is correct
14 Correct 41 ms 2940 KB Output is correct
15 Correct 28 ms 2004 KB Output is correct
16 Correct 35 ms 3092 KB Output is correct
17 Correct 35 ms 3136 KB Output is correct
18 Correct 40 ms 3116 KB Output is correct
19 Correct 47 ms 3180 KB Output is correct
20 Correct 35 ms 3120 KB Output is correct
21 Correct 44 ms 3052 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 288 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 284 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 280 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 0 ms 284 KB Output is correct
10 Correct 1 ms 216 KB Output is correct
11 Correct 0 ms 216 KB Output is correct
12 Correct 1 ms 216 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 2 ms 304 KB Output is correct
15 Correct 2 ms 344 KB Output is correct
16 Correct 1 ms 292 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Correct 1 ms 216 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Correct 1 ms 300 KB Output is correct
21 Correct 2 ms 344 KB Output is correct
22 Correct 2 ms 344 KB Output is correct
23 Correct 2 ms 344 KB Output is correct
24 Correct 2 ms 296 KB Output is correct
25 Correct 190 ms 11984 KB Output is correct
26 Correct 286 ms 12112 KB Output is correct
27 Correct 354 ms 13092 KB Output is correct
28 Correct 327 ms 13536 KB Output is correct
29 Correct 375 ms 13580 KB Output is correct
30 Correct 136 ms 7316 KB Output is correct
31 Correct 175 ms 12928 KB Output is correct
32 Correct 206 ms 13688 KB Output is correct
33 Correct 182 ms 13204 KB Output is correct
34 Correct 225 ms 13512 KB Output is correct
35 Correct 206 ms 13056 KB Output is correct
36 Correct 217 ms 13324 KB Output is correct
37 Correct 197 ms 12032 KB Output is correct