oj.uz

Submission #671175

# Submission time Handle Problem Language Result Execution time Memory
671175 2022-12-12T09:22:35 Z fatemetmhr Palembang Bridges (APIO15_bridge) C++17
100 / 100
 141 ms 26312 KB 
// fikhshal chye daram code miznm :}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 3e5 + 10;

ll sumrbef[2], cntbef[2], sumlaf[2], cntaf[2], ans[2];
ll pref[maxn5], suf[maxn5];
ll ind[2], per[maxn5], l[maxn5], r[maxn5];
int idl[maxn5], idr[maxn5];
vector <int> st[maxn5], ft[maxn5], pt;

inline bool cmp(int i, int j){return l[i] + r[i] < l[j] + r[j];}

inline void add_seg(int id){
    id = per[id];
    st[idl[id]].pb(id);
    ft[idr[id]].pb(id);
    for(int t = 0; t < 2; t++) if(ind[t] >= 0 && ind[t] < pt.size()){
        ll ver = pt[ind[t]];
        if(r[id] < ver){
            cntbef[t]++;
            sumrbef[t] += r[id];
            ans[t] += ver - r[id];
        }
        else if(l[id] > ver){
            cntaf[t]++;
            sumlaf[t] += l[id];
            ans[t] += l[id] - ver;
        }
    }
    return;
}

inline void inc(){
    ind[1]++;
    if(ind[1] == pt.size())
        return;
    ll ver = pt[ind[1]];
    for(auto id : ft[ind[1] - 1]){
        cntbef[1]++;
        sumrbef[1] += r[id];
    }
    for(auto id : st[ind[1]]){
        cntaf[1]--;
        sumlaf[1] -= l[id];
    }
    ans[1] = cntbef[1] *  ver - sumrbef[1] + sumlaf[1] - cntaf[1] * ver;
}

inline void dec(){
    ind[1]--;
    if(ind[1] < 0)
        return;
    ll ver = pt[ind[1]];
    for(auto id : ft[ind[1]]){
        cntbef[1]--;
        sumrbef[1] -= r[id];
    }
    for(auto id : st[ind[1] + 1]){
        cntaf[1]++;
        sumlaf[1] += l[id];
    }
    ans[1] = cntbef[1] *  ver - sumrbef[1] + sumlaf[1] - cntaf[1] * ver;
}

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

    int n, k; cin >> k >> n;
    ll all = 0;
    int m = 0;
    for(int i = 0; i < n; i++){
        char c1, c2;
        cin >> c1 >> l[i] >> c2 >> r[i];
        if(l[i] > r[i])
            swap(l[i], r[i]);
        all += r[i] - l[i];
        if(c1 != c2){
            all++;
            per[m++] = i;
            pt.pb(l[i]); pt.pb(r[i]);
        }
    }

    sort(all(pt));
    pt.resize(unique(all(pt)) - pt.begin());

    for(int i = 0; i < n; i++){
        idl[i] = lower_bound(all(pt), l[i]) - pt.begin();
        idr[i] = lower_bound(all(pt), r[i]) - pt.begin();
    }

    /*
    cout << "Points " << endl;

    for(auto u : pt)
        cout << u << ' ';
    cout << endl;
    */


    sort(per, per + m, cmp); // bar hasbe l + r;

    //for(int i = 0; i < m; i++)
    //    cout << "segment of " << per[i] << ' ' << l[per[i]] << ' ' << r[per[i]] << endl;

    sumrbef[0] = 0; cntbef[0] = 0; sumlaf[0] = 0; cntaf[0] = 0;
    sumrbef[1] = 0; cntbef[1] = 0; sumlaf[1] = 0; cntaf[1] = 0;
    ans[0] = ans[1] = 0;
    ind[0] = 0; ind[1] = 1;
    for(int i = 0; i < m; i++){
        add_seg(i);
        while(ind[1] < pt.size() && ans[0] > ans[1]){
            ind[0] = ind[1];
            sumrbef[0] = sumrbef[1];
            cntbef[0] = cntbef[1];
            sumlaf[0] = sumlaf[1];
            cntaf[0] = cntaf[1];
            ans[0] = ans[1];
            inc();
        }
        pref[i] = ans[0];
        //cout << i << ' ' << ind[0] << ' ' << ind[1] << ' '<< ans[0] << ' ' << ans[1] << endl;
    }

    //cout << "all " << all << endl;

    if(k == 1)
        return cout << pref[m - 1] * 2 + all << endl, 0;

    for(int i = 0; i < pt.size(); i++){
        st[i].clear();
        ft[i].clear();
    }


    sumrbef[0] = 0; cntbef[0] = 0; sumlaf[0] = 0; cntaf[0] = 0;
    sumrbef[1] = 0; cntbef[1] = 0; sumlaf[1] = 0; cntaf[1] = 0;
    ans[0] = ans[1] = 0;
    ind[0] = int(pt.size()) - 1; ind[1] = int(pt.size()) - 2; 
    for(int i = m - 1; i >= 0; i--){
        add_seg(i);
        while(ind[1] >= 0 && ans[0] >= ans[1]){
            ind[0] = ind[1];
            sumrbef[0] = sumrbef[1];
            cntbef[0] = cntbef[1];
            sumlaf[0] = sumlaf[1];
            cntaf[0] = cntaf[1];
            ans[0] = ans[1];
            dec();
        }
        suf[i] = ans[0];
        //cout << "suff " << i << ' ' << ind[0] << ' ' << ind[1] << ' '<< ans[0] << ' ' << ans[1] << endl;

    }

    ll ans = min(pref[m - 1], suf[0]);

    for(int i = 0; i < m - 1; i++)
        ans = min(ans, pref[i] + suf[i + 1]);

    cout << ans * 2 + all << endl;
}

/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7


2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

*/

Compilation message

bridge.cpp: In function 'void add_seg(int)':
bridge.cpp:28:57: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int t = 0; t < 2; t++) if(ind[t] >= 0 && ind[t] < pt.size()){
      |                                                  ~~~~~~~^~~~~~~~~~~
bridge.cpp: In function 'void inc()':
bridge.cpp:46:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     if(ind[1] == pt.size())
      |        ~~~~~~~^~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:123:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         while(ind[1] < pt.size() && ans[0] > ans[1]){
      |               ~~~~~~~^~~~~~~~~~~
bridge.cpp:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(int i = 0; i < pt.size(); i++){
      |                    ~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14372 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14564 KB Output is correct
5 Correct 8 ms 14496 KB Output is correct
6 Correct 9 ms 14548 KB Output is correct
7 Correct 8 ms 14560 KB Output is correct
8 Correct 9 ms 14576 KB Output is correct
9 Correct 8 ms 14476 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14548 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14564 KB Output is correct
5 Correct 9 ms 14540 KB Output is correct
6 Correct 8 ms 14444 KB Output is correct
7 Correct 8 ms 14492 KB Output is correct
8 Correct 8 ms 14676 KB Output is correct
9 Correct 8 ms 14452 KB Output is correct
10 Correct 8 ms 14488 KB Output is correct
11 Correct 8 ms 14548 KB Output is correct
12 Correct 38 ms 20740 KB Output is correct
13 Correct 119 ms 25384 KB Output is correct
14 Correct 71 ms 19952 KB Output is correct
15 Correct 67 ms 20812 KB Output is correct
16 Correct 40 ms 20348 KB Output is correct
17 Correct 60 ms 25400 KB Output is correct
18 Correct 67 ms 25484 KB Output is correct
19 Correct 95 ms 25384 KB Output is correct
20 Correct 43 ms 20260 KB Output is correct
21 Correct 75 ms 25396 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 9 ms 14448 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 9 ms 14432 KB Output is correct
8 Correct 9 ms 14420 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 8 ms 14428 KB Output is correct
14 Correct 8 ms 14432 KB Output is correct
15 Correct 9 ms 14548 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 9 ms 14472 KB Output is correct
18 Correct 9 ms 14416 KB Output is correct
19 Correct 8 ms 14548 KB Output is correct
20 Correct 9 ms 14548 KB Output is correct
21 Correct 8 ms 14548 KB Output is correct
22 Correct 9 ms 14548 KB Output is correct
23 Correct 8 ms 14472 KB Output is correct
24 Correct 9 ms 14480 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14448 KB Output is correct
2 Correct 9 ms 14424 KB Output is correct
3 Correct 8 ms 14424 KB Output is correct
4 Correct 9 ms 14488 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 9 ms 14420 KB Output is correct
9 Correct 8 ms 14376 KB Output is correct
10 Correct 8 ms 14368 KB Output is correct
11 Correct 8 ms 14452 KB Output is correct
12 Correct 8 ms 14456 KB Output is correct
13 Correct 8 ms 14428 KB Output is correct
14 Correct 8 ms 14428 KB Output is correct
15 Correct 9 ms 14548 KB Output is correct
16 Correct 8 ms 14424 KB Output is correct
17 Correct 9 ms 14420 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14436 KB Output is correct
20 Correct 8 ms 14536 KB Output is correct
21 Correct 8 ms 14516 KB Output is correct
22 Correct 8 ms 14600 KB Output is correct
23 Correct 9 ms 14528 KB Output is correct
24 Correct 9 ms 14548 KB Output is correct
25 Correct 42 ms 21620 KB Output is correct
26 Correct 60 ms 21068 KB Output is correct
27 Correct 135 ms 25924 KB Output is correct
28 Correct 140 ms 26276 KB Output is correct
29 Correct 141 ms 26288 KB Output is correct
30 Correct 69 ms 20676 KB Output is correct
31 Correct 49 ms 21292 KB Output is correct
32 Correct 66 ms 26232 KB Output is correct
33 Correct 69 ms 26312 KB Output is correct
34 Correct 104 ms 26224 KB Output is correct
35 Correct 46 ms 21188 KB Output is correct
36 Correct 80 ms 26228 KB Output is correct
37 Correct 37 ms 21332 KB Output is correct