oj.uz

Submission #1095173

# Submission time Handle Problem Language Result Execution time Memory
1095173 2024-10-01T13:21:59 Z NguyenPhucThang Palembang Bridges (APIO15_bridge) C++17
22 / 100
 97 ms 14552 KB 
#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int base = 31;
const ll mod = 1e9 + 7;
const ll oo = 1e16;
const int N = 2e5 + 5;
const int M = 2e5;


vector<pll> v;
vector<ll> nen;

bool cmp(pii a, pii b){
    return (a.fi + a.se) < (b.fi + b.se);
}

struct node{
    ll cnt, sum;
};

struct segtree{
    node st[4 * N];

    node combine(node a, node b){
        return {a.cnt + b.cnt, a.sum + b.sum};
    }

    void update(int id, int l, int r, int i, int v){
        if (i < l || r < i) return;
        if (l == r){
            st[id].cnt += v;
            st[id].sum = nen[l - 1] * st[id].cnt;
            return;
        }

        int mid = (l + r) >> 1;
        update(2 * id, l, mid, i, v), update(2 * id + 1, mid + 1, r, i, v);
        st[id] = combine(st[2 * id], st[2 * id + 1]);
    }

    node get(int id, int l, int r, int u, int v){
        if (v < l || r < u) return {0, 0};
        if (u <= l && r <= v) return st[id];
        int mid = (l + r) >> 1;
        return combine(get(2 * id, l, mid, u, v), get(2 * id + 1, mid + 1, r, u, v));
    }

    int find_kth(int id, int l, int r, int k){
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (st[2 * id].cnt >= k) return find_kth(2 * id, l, mid, k);
        return find_kth(2 * id + 1, mid + 1, r, k - st[2 * id].cnt);
    }

    ll find_cost(int sz){
        ll cmed = find_kth(1, 1, M, (1 + sz) >> 1);
        ll med = nen[cmed - 1];
        node lower_ans = get(1, 1, M, 1, cmed);
        node higher_ans = get(1, 1, M, cmed + 1, M);
        return med * lower_ans.cnt - lower_ans.sum + higher_ans.sum - med * higher_ans.cnt;
    }

} Left, Right, All;


int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

    int K, n;
    cin >> K >> n;

    ll res = 0;

    forr(i, 1, n) {
        char b1, b2;
        int x1, x2;
        cin >> b1 >> x1 >> b2 >> x2;
        if (b1 == b2) res += abs(x1 - x2);
        else{
            res++;
            v.pb({x1, x2});
            nen.pb(x1);
            nen.pb(x2);
         }
    }



    // K = 1
   
   ll cost1 = 0;

   if (v.size() >= 1){

      sort(all(v), cmp);


      sort(all(nen));
      nen.resize(unique(all(nen)) - nen.begin());
      forr(i, 0, v.size() - 1){
         v[i].fi = lower_bound(all(nen), v[i].fi) - nen.begin() + 1;
         v[i].se = lower_bound(all(nen), v[i].se) - nen.begin() + 1;
      }
      forf(i, 0, v.size()){
         All.update(1, 1, M, v[i].fi, 1);
         All.update(1, 1, M, v[i].se, 1);
      }
      cost1 = All.find_cost(2 * v.size());
   }


   // ll cost2 = oo;

   // if (K == 2 && v.size() >= 2){
   //    forf(i, 0, v.size()) {
   //       Right.update(1, 1, M, v[i].fi, 1);
   //       Right.update(1, 1, M, v[i].se, 1);
   //    }

   //    int cntLeft = 0;
   //    forr(i, 0, v.size() - 2){
   //       Left.update(1, 1, M, v[i].fi, 1);
   //       Left.update(1, 1, M, v[i].se, 1);
   //       Right.update(1, 1, M, v[i].fi, -1);
   //       Right.update(1, 1, M, v[i].se, -1);
   //       cntLeft++;
   //       cost2 = min(cost2, Left.find_cost(2 * cntLeft) + Right.find_cost(2 * (v.size() - cntLeft)));
   //    }
   // }

   cout << res + cost1 << endl;

    return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:2:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define forr(i, a, b) for (int i = (a); i <= (b); i++)
      |                                           ^
bridge.cpp:120:7: note: in expansion of macro 'forr'
  120 |       forr(i, 0, v.size() - 1){
      |       ^~~~
bridge.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(i, a, b) for (int i = (a); i < (b); i++)
      |                                           ^
bridge.cpp:124:7: note: in expansion of macro 'forf'
  124 |       forf(i, 0, v.size()){
      |       ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 540 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 37 ms 4544 KB Output is correct
13 Correct 97 ms 14552 KB Output is correct
14 Correct 59 ms 5036 KB Output is correct
15 Correct 51 ms 8640 KB Output is correct
16 Correct 39 ms 5300 KB Output is correct
17 Correct 51 ms 14256 KB Output is correct
18 Correct 58 ms 13788 KB Output is correct
19 Correct 67 ms 13804 KB Output is correct
20 Correct 42 ms 5560 KB Output is correct
21 Correct 64 ms 13976 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 37.0

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