Submission #725317

#	Time	Username	Problem	Language	Result	Execution time	Memory
725317		quiet_space	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	88 ms	5968 KiB

bridge

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
using ll = long long;
using pii = std::pair <int, int>;
const int maxn = 100005;
inline bool cmp (pii p, pii q) {
  return p.first + p.second < q.first + q.second;
}
char chp[5], chq[5];
pii p[maxn];
int a[maxn<<1];
ll pre[maxn], suf[maxn];
struct Node1 {
  ll tot; std::priority_queue <int> q;
  inline int top (void) { return q.top(); }
  inline void push (int v) { tot += v; q.push(v); }
  inline void pop (void) { tot -= q.top(); q.pop(); }
  inline void clear (void) { tot = 0; while(!q.empty()) q.pop(); }
} q1;
struct Node2 {
  ll tot; std::priority_queue <int, std::vector <int>, std::greater <int> > q;
  inline int top (void) { return q.top(); }
  inline void push (int v) { tot += v; q.push(v); }
  inline void pop (void) { tot -= q.top(); q.pop(); }
  inline void clear (void) { tot = 0; while(!q.empty()) q.pop(); }
} q2;
int main (void) {
  int k = read(), N = read(), n = 0;
  ll ans = 0;
  FOR(i,1,N) {
    scanf("%s", chp+1);
    int s = read();
    scanf("%s", chq+1);
    int t = read();
    if(s > t) std::swap (s, t);
    if(chp[1] == chq[1])
      ans += t - s;
    else {
      ++ ans;
      p[++ n] = {s, t};
    }
  }
  if(k == 1) {
    FOR(i,1,n) a[i*2-1] = p[i].first, a[i*2] = p[i].second;
    std::sort(a+1, a+n*2+1);
    FOR(i,1,n) ans -= a[i];
    FOR(i,n+1,n*2) ans += a[i];
  } else {
    std::sort(p+1, p+n+1, cmp);
    ll mn = 1ll << 60;
    FOR(i,1,n) {
      q1.push(p[i].first);
      q2.push(p[i].second);
      while(q1.top() > q2.top()) {
        q2.push(q1.top()); q1.pop();
        q1.push(q2.top()); q2.pop();
      }
      pre[i] = q2.tot - q1.tot;
    }
    q1.clear (); q2.clear ();
    ROF(i,n,1) {
      q1.push(p[i].first);
      q2.push(p[i].second);
      while(q1.top() > q2.top()) {
        q2.push(q1.top()); q1.pop();
        q1.push(q2.top()); q2.pop();
      }
      suf[i] = q2.tot - q1.tot;
    }
    FOR(i,0,n) mn = std::min(mn, pre[i] + suf[i+1]);
    ans += mn;
  }
  printf("%lld\n", ans);
  return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%s", chp+1);
      |     ~~~~~^~~~~~~~~~~~~
bridge.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%s", chq+1);
      |     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37