oj.uz

답안 #699922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699922 2023-02-18T10:44:26 Z Abrar_Al_Samit Palembang Bridges (APIO15_bridge) C++17
0 / 100
 1 ms 212 KB 
#include<bits/stdc++.h>
using namespace std;

#define ub upper_bound
const long long INF = 1e18;
void PlayGround() {
  int k, n;
  cin>>k>>n;

  long long ans = 0, S = 0;

  int s[n], t[n];

  vector<int>pts;

  vector<pair<int,int>>a, b;
  for(int i=0; i<n; ++i) {
    char p, q;
    cin>>p>>s[i]>>q>>t[i];
    if(s[i]>t[i]) swap(s[i], t[i]);
    if(p==q) {
      ans += abs(s[i]-t[i]);
      --i;
      --n;
    } else {
      a.emplace_back(s[i], t[i]);
      b.emplace_back(t[i], s[i]);
      pts.push_back(s[i]);
      pts.push_back(t[i]);
      S += t[i] - s[i];
    }
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  ans += n;

  long long pre[n], suf[n];
  long long p1[n], s1[n];
  for(int i=0; i<n; ++i) {
    pre[i] = -(b[i].first+b[i].second);
    p1[i] = b[i].first-b[i].second;
    if(i) {
      pre[i] += pre[i-1];
      p1[i] += p1[i-1];
    }
  }

  for(int i=n-1; i>=0; --i) {
    suf[i] = a[i].first+a[i].second;
    s1[i] = a[i].second-a[i].first;
    if(i<n-1) {
      suf[i] += suf[i+1];
      s1[i] += s1[i+1];
    }
  }

  sort(pts.begin(), pts.end());
  pts.resize(unique(pts.begin(), pts.end())-pts.begin());

  int m = pts.size();

  long long best = INF;
  for(int x : pts) {
    int j1 = ub(b.begin(), b.end(), make_pair(x, -1)) - b.begin() - 1;
    int j2 = ub(a.begin(), a.end(), make_pair(x, -1)) - a.begin();

    int c1 = j1+1, c2 = (n-j2);

    long long cur = S;
    if(c1) {
      cur += pre[j1] + c1 * 2LL * x;
      cur -= p1[j1];
    }
    if(c2) {
      cur += suf[j2] - c2 * 2LL * x;
      cur -= s1[j2];
    }
    best = min(best, cur);
  }
  ans += best;
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Compilation message

bridge.cpp: In function 'void PlayGround()':
bridge.cpp:61:7: warning: unused variable 'm' [-Wunused-variable]
   61 |   int m = pts.size();
      |       ^

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -