oj.uz

Submission #882623

# Submission time Handle Problem Language Result Execution time Memory
882623 2023-12-03T12:21:26 Z vjudge1 Palembang Bridges (APIO15_bridge) C++17
31 / 100
 2000 ms 110276 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;



ll solv(vector<pair<ll, ll>> &v){
  if(v.size() == 0) return 0ll;
  vector<pair<ll, ll>> pref(v.size());
  vector<pair<ll, ll>> suf(v.size());
  pref[0] = {0, 0};
  for(int i = 1; i < v.size(); ++i){
    pref[i] = pref[i - 1];
    if(v[i].second == 1) pref[i].first += v[i].first, pref[i].second++;
  }
  suf[v.size() - 1] = {0, 0};
  for(int i = v.size() - 2; i >= 0; --i){
    suf[i] = suf[i + 1];
    if(v[i].second == 0) suf[i].first += v[i].first, suf[i].second++;
  }
  ll best = 1e18;
  for(int i = 0; i < v.size(); ++i){
    if(abs(suf[i].second - pref[i].second) <= 1)
    best = min(best, suf[i].first - pref[i].first + (v[i].first * pref[i].second) - (v[i].first * suf[i].second));
  }
  return best*2;
}

int k, n;
ll ans = 0;
pair<ll, ll> pref[N], suf[N], prefL[N], sufR[N];
array<ll, 2> a[N];
vector<int> L[N];
set<int> R[N];

void solve(){
  cin >> k >> n;
  int c = 0;
  for(int i = 1; i <= n; ++i){
    char c1, c2; ll x1, x2; cin >> c1 >> x1 >> c2 >> x2;
    if(c1 == c2){
      ans += abs(x1-x2);
    }else{
      ++c;
      a[c][0] = min(x1, x2);
      a[c][1] = max(x1, x2);
      ans += abs(x1-x2);
      // cout << a[c][0] << ' '<< a[c][1] << '\n';
    }
  }
  n = c;
  if(n==0){
    cout << ans;
    return;
  }
  sort(a+1, a+1+n);

  vector<pair<ll, ll>> v;
  vector<array<ll, 3>> vv;
  for(int i = 1; i <= n; ++i) v.pb({a[i][0], 0}), v.pb({a[i][1], 1});
  for(int i = 1; i <= n; ++i) vv.pb({a[i][0], 0, i}), vv.pb({a[i][1], 1, i});

  sort(all(v));
  sort(all(vv));
  pref[0] = {0, 0};
  prefL[0] = {0, 0};
  for(int i = 1; i < v.size(); ++i){
    pref[i] = pref[i - 1];
    prefL[i] = prefL[i - 1];
    if(v[i].second == 1) pref[i].first += v[i].first, pref[i].second++;
    if(v[i].second == 0) prefL[i].first += v[i].first, prefL[i].second++;
  }

  suf[v.size() - 1] = {0, 0};
  sufR[v.size() - 1] = {0, 0};
  for(int i = v.size() - 2; i >= 0; --i){
    suf[i] = suf[i + 1];
    sufR[i] = sufR[i + 1];
    if(v[i].second == 0) suf[i].first += v[i].first, suf[i].second++;
    if(v[i].second == 1) sufR[i].first += v[i].first, sufR[i].second++;
  }

  if(k == 1){
    ll best = 1e18;
    for(int i = 0; i < v.size(); ++i){
      if(abs(suf[i].second - pref[i].second) <= 1)
      best = min(best, suf[i].first - pref[i].first + (v[i].first * pref[i].second) - (v[i].first * suf[i].second));
    }
    cout << ans + best*2 + n; 
  }else{
    ll best = 1e18;

    for(int i = 0; i < n*2; ++i){
      for(int j = i + 1; j < 2*n; ++j){
        ll s = 0;
        for(int k = 1; k <= n; ++k){
          if(a[k][0] <= v[i].first && a[k][1] >= v[i].first) continue;
          if(a[k][0] <= v[j].first && a[k][1] >= v[j].first) continue;
          s += 2*min({abs(v[i].first - a[k][0]), abs(v[i].first - a[k][1]), abs(v[j].first - a[k][0]), abs(v[j].first - a[k][1])});
        }
        best = min(best, s);
      }
    }
    cout << ans + best + n;
    return;


    suf[2*n] = {0, 0};
    for(int i = 0; i < v.size(); ++i) R[pref[i].second - suf[i].second + M].insert(i);
    for(int i = 0; i < v.size(); ++i){
      if(abs(suf[i].second - pref[i].second) <= 1)
        best = min(best, suf[i].first - pref[i].first + (v[i].first * pref[i].second) - (v[i].first * suf[i].second));
    }
    for(int i = 0; i < v.size(); ++i){
      int x = pref[i].second - suf[i].second + M;
      L[x].pb(i);
      R[x].erase(i);
      
      int y = suf[i + 1].second;
      int y2 = -pref[i].second;
      for(int j = y + M - 2; j <= y + M + 2; ++j){
        for(int j2 = y2 + M - 2; j2 <= y2 + M + 2; ++j2){
          for(auto l: L[j]){
            for(auto r: R[j2]){
              best = min(best,
                (suf[l].first - suf[i + 1].first) - pref[l].first + (pref[l].second - (suf[l].second - suf[i + 1].second)) * v[l].first + 
                suf[r].first - (pref[r].first - pref[i].first) + ((pref[r].second - pref[i].second) - suf[r].second) * v[r].first 
              );
            }
          }
        }
      }
    }
    cout << ans + 2*best + n;
  }

}



int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

bridge.cpp: In function 'long long int solv(std::vector<std::pair<long long int, long long int> >&)':
bridge.cpp:19:20: 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]
   19 |   for(int i = 1; i < v.size(); ++i){
      |                  ~~^~~~~~~~~~
bridge.cpp:29:20: 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]
   29 |   for(int i = 0; i < v.size(); ++i){
      |                  ~~^~~~~~~~~~
bridge.cpp: In function 'void solve()':
bridge.cpp:74:20: 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]
   74 |   for(int i = 1; i < v.size(); ++i){
      |                  ~~^~~~~~~~~~
bridge.cpp:92: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]
   92 |     for(int i = 0; i < v.size(); ++i){
      |                    ~~^~~~~~~~~~
bridge.cpp:116: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]
  116 |     for(int i = 0; i < v.size(); ++i) R[pref[i].second - suf[i].second + M].insert(i);
      |                    ~~^~~~~~~~~~
bridge.cpp:117: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]
  117 |     for(int i = 0; i < v.size(); ++i){
      |                    ~~^~~~~~~~~~
bridge.cpp:121: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]
  121 |     for(int i = 0; i < v.size(); ++i){
      |                    ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:150:15: warning: unused variable 'aa' [-Wunused-variable]
  150 |   int tt = 1, aa;
      |               ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 72284 KB Output is correct
2 Correct 14 ms 72284 KB Output is correct
3 Correct 18 ms 80732 KB Output is correct
4 Correct 16 ms 80732 KB Output is correct
5 Correct 16 ms 80732 KB Output is correct
6 Correct 16 ms 80984 KB Output is correct
7 Correct 16 ms 80732 KB Output is correct
8 Correct 16 ms 80732 KB Output is correct
9 Correct 20 ms 80728 KB Output is correct
10 Correct 16 ms 80728 KB Output is correct
11 Correct 20 ms 80732 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 72284 KB Output is correct
2 Correct 14 ms 72284 KB Output is correct
3 Correct 18 ms 80732 KB Output is correct
4 Correct 17 ms 80732 KB Output is correct
5 Correct 19 ms 80732 KB Output is correct
6 Correct 16 ms 80608 KB Output is correct
7 Correct 19 ms 80728 KB Output is correct
8 Correct 16 ms 80728 KB Output is correct
9 Correct 16 ms 80732 KB Output is correct
10 Correct 16 ms 80616 KB Output is correct
11 Correct 16 ms 80732 KB Output is correct
12 Correct 63 ms 110276 KB Output is correct
13 Correct 82 ms 110012 KB Output is correct
14 Correct 84 ms 105056 KB Output is correct
15 Correct 57 ms 94916 KB Output is correct
16 Correct 69 ms 107868 KB Output is correct
17 Correct 62 ms 107868 KB Output is correct
18 Correct 64 ms 108896 KB Output is correct
19 Correct 63 ms 107880 KB Output is correct
20 Correct 71 ms 108276 KB Output is correct
21 Correct 62 ms 109896 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 72348 KB Output is correct
2 Correct 15 ms 72284 KB Output is correct
3 Correct 18 ms 80476 KB Output is correct
4 Correct 20 ms 80644 KB Output is correct
5 Correct 17 ms 80544 KB Output is correct
6 Correct 16 ms 80476 KB Output is correct
7 Correct 17 ms 80640 KB Output is correct
8 Correct 22 ms 80644 KB Output is correct
9 Correct 20 ms 80476 KB Output is correct
10 Correct 22 ms 80476 KB Output is correct
11 Correct 20 ms 80684 KB Output is correct
12 Correct 22 ms 80672 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 72284 KB Output is correct
2 Correct 16 ms 72452 KB Output is correct
3 Correct 20 ms 80476 KB Output is correct
4 Correct 19 ms 80608 KB Output is correct
5 Correct 17 ms 80476 KB Output is correct
6 Correct 17 ms 80660 KB Output is correct
7 Correct 17 ms 80564 KB Output is correct
8 Correct 22 ms 80560 KB Output is correct
9 Correct 22 ms 80676 KB Output is correct
10 Correct 23 ms 80480 KB Output is correct
11 Correct 22 ms 80824 KB Output is correct
12 Correct 23 ms 80688 KB Output is correct
13 Execution timed out 2086 ms 80580 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 72336 KB Output is correct
2 Correct 16 ms 72280 KB Output is correct
3 Correct 17 ms 80680 KB Output is correct
4 Correct 20 ms 80644 KB Output is correct
5 Correct 17 ms 80636 KB Output is correct
6 Correct 17 ms 80476 KB Output is correct
7 Correct 18 ms 80472 KB Output is correct
8 Correct 24 ms 80860 KB Output is correct
9 Correct 20 ms 80684 KB Output is correct
10 Correct 23 ms 80564 KB Output is correct
11 Correct 21 ms 80640 KB Output is correct
12 Correct 22 ms 80644 KB Output is correct
13 Execution timed out 2075 ms 80792 KB Time limit exceeded
14 Halted 0 ms 0 KB -