oj.uz

답안 #700623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
700623 2023-02-19T07:55:36 Z Abrar_Al_Samit Palembang Bridges (APIO15_bridge) C++17
22 / 100
 117 ms 9048 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 += t[i] - s[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());

  if(n==0) {
    cout<<ans<<'\n';
    return;
  }

  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:66:7: warning: unused variable 'm' [-Wunused-variable]
   66 |   int m = pts.size();
      |       ^

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 368 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 412 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 360 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 372 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 45 ms 7416 KB Output is correct
13 Correct 117 ms 8988 KB Output is correct
14 Correct 72 ms 7180 KB Output is correct
15 Correct 57 ms 5492 KB Output is correct
16 Correct 40 ms 8380 KB Output is correct
17 Correct 69 ms 9048 KB Output is correct
18 Correct 60 ms 8672 KB Output is correct
19 Correct 104 ms 9048 KB Output is correct
20 Correct 52 ms 8504 KB Output is correct
21 Correct 93 ms 8796 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 37.0

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