oj.uz

Submission #671174

# Submission time Handle Problem Language Result Execution time Memory
671174 2022-12-12T09:22:06 Z fatemetmhr Palembang Bridges (APIO15_bridge) C++17
100 / 100
 155 ms 28500 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 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14488 KB Output is correct
5 Correct 9 ms 14476 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 8 ms 14428 KB Output is correct
11 Correct 8 ms 14476 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14424 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14428 KB Output is correct
4 Correct 8 ms 14552 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 8 ms 14568 KB Output is correct
9 Correct 10 ms 14548 KB Output is correct
10 Correct 8 ms 14516 KB Output is correct
11 Correct 8 ms 14572 KB Output is correct
12 Correct 37 ms 20632 KB Output is correct
13 Correct 134 ms 25340 KB Output is correct
14 Correct 72 ms 19888 KB Output is correct
15 Correct 68 ms 20908 KB Output is correct
16 Correct 40 ms 20360 KB Output is correct
17 Correct 67 ms 25340 KB Output is correct
18 Correct 64 ms 25408 KB Output is correct
19 Correct 95 ms 25356 KB Output is correct
20 Correct 43 ms 20272 KB Output is correct
21 Correct 77 ms 25340 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 14336 KB Output is correct
3 Correct 8 ms 14440 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14424 KB Output is correct
6 Correct 10 ms 14424 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 8 ms 14424 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14444 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14376 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 14420 KB Output is correct
5 Correct 8 ms 14368 KB Output is correct
6 Correct 8 ms 14364 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 8 ms 14368 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 9 ms 14428 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 8 ms 14432 KB Output is correct
15 Correct 9 ms 14568 KB Output is correct
16 Correct 8 ms 14424 KB Output is correct
17 Correct 8 ms 14424 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14548 KB Output is correct
20 Correct 8 ms 14548 KB Output is correct
21 Correct 9 ms 14500 KB Output is correct
22 Correct 9 ms 14496 KB Output is correct
23 Correct 9 ms 14532 KB Output is correct
24 Correct 9 ms 14548 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14424 KB Output is correct
6 Correct 8 ms 14424 KB Output is correct
7 Correct 8 ms 14388 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 8 ms 14416 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14424 KB Output is correct
12 Correct 8 ms 14452 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 9 ms 14464 KB Output is correct
15 Correct 9 ms 14560 KB Output is correct
16 Correct 8 ms 14424 KB Output is correct
17 Correct 8 ms 14508 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 10 ms 14548 KB Output is correct
20 Correct 8 ms 14548 KB Output is correct
21 Correct 8 ms 14548 KB Output is correct
22 Correct 9 ms 14564 KB Output is correct
23 Correct 9 ms 14548 KB Output is correct
24 Correct 9 ms 14548 KB Output is correct
25 Correct 40 ms 22256 KB Output is correct
26 Correct 60 ms 21948 KB Output is correct
27 Correct 139 ms 27516 KB Output is correct
28 Correct 155 ms 28500 KB Output is correct
29 Correct 143 ms 28424 KB Output is correct
30 Correct 70 ms 21784 KB Output is correct
31 Correct 44 ms 22756 KB Output is correct
32 Correct 74 ms 28468 KB Output is correct
33 Correct 72 ms 28144 KB Output is correct
34 Correct 108 ms 28488 KB Output is correct
35 Correct 47 ms 22868 KB Output is correct
36 Correct 81 ms 28272 KB Output is correct
37 Correct 38 ms 21960 KB Output is correct