oj.uz

Submission #673567

# Submission time Handle Problem Language Result Execution time Memory
673567 2022-12-21T06:06:28 Z Cookie Palembang Bridges (APIO15_bridge) C++14
100 / 100
 116 ms 9800 KB 
#include<bits/stdc++.h>
#pragma GCC target("popcnt")
using namespace std;

 
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#include<fstream>
ifstream fin("cowpatibility.in");
ofstream fout("cowpatibility.out");
#define pii pair<int, int>
#define pll pair<ll, ll>

const ll mod = 1e9 + 7, mod2 = 1e9 + 9;
const int mxn = 2e5;
int k, n;
ll ans = 0;
struct BIT{
    ll bit[mxn + 1];
    void init(){
        for(int i = 0; i <= mxn; i++)bit[i] = 0;
    }
    void upd(int p, ll v){
        p--;
        while(p <= mxn){
            bit[p] += v;
            
            p |= (p + 1);
        }
    
    }
    ll get(int p){
        ll ans = 0;
        while(p > 0){
            ans += bit[p - 1];
            p &= (p - 1);
        }
        return(ans);
    }
    int kth(int x){
        int p = 0;
        
        for(int i = 1 << 17; i; i >>= 1){
           
            if(p + i <= mxn && bit[p + i - 1] < x){
                p += i; x -= bit[p - 1];
            }
        }
        return(p);
    }
};
BIT cnt, sm;
vt<ll>comp;
ll p[mxn + 1];
vt<pll>v;

void solve1(){
    vt<ll>points;
    for(auto [aa, bb]: v){
        points.pb(aa); points.pb(bb);
    }
    sort(points.begin(), points.end());
    ll med = points[points.size() / 2];
    for(int i = 0; i < points.size(); i++){
        ans += abs(med - points[i]);
    }
    cout << ans;
    
}
bool cmp(pll a, pll b){
    return((a.fi + a.se) < (b.fi + b.se));
}
void add(ll x){
    //cout << comp[x - 1] << " ";
    cnt.upd(x, 1); sm.upd(x, comp[x - 1]);
}
ll gett(int x){
    
    
    ll ans = sm.get(mxn) - sm.get(x) - (cnt.get(mxn) - cnt.get(x)) * comp[x - 1];
    //cout << ans << " ";
    ans += cnt.get(x) * comp[x - 1] - sm.get(x);
    
    //cout << ans << " ";
    return(ans);
}
int med(int kk){
    int len = (kk + 1) / 2;
    int pos = cnt.kth(len);
    
    return(pos + 1);
}
void solve2(){
    
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < v.size(); i++){
        comp.pb(v[i].fi); comp.pb(v[i].se);
    }
    sort(comp.begin(), comp.end());
    for(int i = 0; i < v.size(); i++){
        v[i].fi = lower_bound(comp.begin(), comp.end(), v[i].fi) - comp.begin() + 1;
        v[i].se = lower_bound(comp.begin(), comp.end(), v[i].se) - comp.begin() + 1;
    }
    
    for(int i = 0; i < v.size(); i++){
        
        add(v[i].fi); add(v[i].se);
        p[i] = gett(med((i + 1) * 2));
        
    }
    
    cnt.init(); sm.init();
    ll res = p[v.size() - 1];
    
    for(int i = v.size() - 1; i >= 1; i--){
        
        add(v[i].fi); add(v[i].se);
        res = min(res, gett(med((v.size() - i) * 2)) + p[i - 1]);
        
    }
    
    cout << ans + res;
    
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> k >> n;
    forr(i, 0, n){
        char a, b; ll aa, bb;
        cin >> a >> aa >> b >> bb;
        if(a == b)ans += abs(aa - bb);
        else v.pb({aa, bb});
    }
    ans += v.size();
    if(k == 1)solve1();
    else solve2();
    return 0;
}

Compilation message

bridge.cpp: In function 'void solve1()':
bridge.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     for(auto [aa, bb]: v){
      |              ^
bridge.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < points.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
bridge.cpp: In function 'void solve2()':
bridge.cpp:102:22: 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]
  102 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
bridge.cpp:106:22: 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]
  106 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
bridge.cpp:111:22: 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]
  111 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 20 ms 4952 KB Output is correct
13 Correct 39 ms 4932 KB Output is correct
14 Correct 28 ms 4752 KB Output is correct
15 Correct 23 ms 2768 KB Output is correct
16 Correct 25 ms 4924 KB Output is correct
17 Correct 28 ms 4940 KB Output is correct
18 Correct 33 ms 5016 KB Output is correct
19 Correct 38 ms 4980 KB Output is correct
20 Correct 27 ms 4956 KB Output is correct
21 Correct 34 ms 4940 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3368 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 2 ms 3412 KB Output is correct
13 Correct 2 ms 3412 KB Output is correct
14 Correct 4 ms 3484 KB Output is correct
15 Correct 3 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct
18 Correct 2 ms 3412 KB Output is correct
19 Correct 2 ms 3540 KB Output is correct
20 Correct 2 ms 3412 KB Output is correct
21 Correct 2 ms 3412 KB Output is correct
22 Correct 2 ms 3412 KB Output is correct
23 Correct 3 ms 3412 KB Output is correct
24 Correct 2 ms 3412 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3536 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 2 ms 3412 KB Output is correct
13 Correct 2 ms 3412 KB Output is correct
14 Correct 3 ms 3540 KB Output is correct
15 Correct 3 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct
18 Correct 2 ms 3412 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 2 ms 3412 KB Output is correct
21 Correct 3 ms 3540 KB Output is correct
22 Correct 3 ms 3412 KB Output is correct
23 Correct 2 ms 3412 KB Output is correct
24 Correct 2 ms 3540 KB Output is correct
25 Correct 52 ms 7492 KB Output is correct
26 Correct 66 ms 7444 KB Output is correct
27 Correct 105 ms 9244 KB Output is correct
28 Correct 114 ms 9732 KB Output is correct
29 Correct 116 ms 9800 KB Output is correct
30 Correct 59 ms 6848 KB Output is correct
31 Correct 60 ms 9060 KB Output is correct
32 Correct 72 ms 9788 KB Output is correct
33 Correct 79 ms 9472 KB Output is correct
34 Correct 79 ms 9736 KB Output is correct
35 Correct 56 ms 9312 KB Output is correct
36 Correct 77 ms 9476 KB Output is correct
37 Correct 54 ms 8228 KB Output is correct