oj.uz

답안 #671167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
671167 2022-12-12T09:13:57 Z fatemetmhr Palembang Bridges (APIO15_bridge) C++17
0 / 100
 11 ms 14592 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];
int 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()){
        int 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;
    int 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;
    int 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 += abs(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: '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: '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: '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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 11 ms 14592 KB Output is correct
4 Correct 10 ms 14548 KB Output is correct
5 Correct 10 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 Incorrect 8 ms 14560 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14408 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 8 ms 14480 KB Output is correct
6 Correct 8 ms 14440 KB Output is correct
7 Correct 8 ms 14564 KB Output is correct
8 Incorrect 8 ms 14560 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14432 KB Output is correct
3 Correct 7 ms 14424 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 14364 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14428 KB Output is correct
9 Incorrect 8 ms 14420 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 9 ms 14352 KB Output is correct
4 Correct 8 ms 14424 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 8 ms 14428 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Incorrect 8 ms 14416 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14364 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Incorrect 8 ms 14420 KB Output isn't correct
10 Halted 0 ms 0 KB -