Submission #14383

#	Time	Username	Problem	Language	Result	Execution time	Memory
14383		tncks0121	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	156 ms	9836 KiB

bridge

#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <time.h>
#include <limits.h>
 
using namespace std;
 
typedef long long ll;
typedef double lf;
 
const int N_ = 100050;
 
int K, N;
 
ll sum_of_same_part;
ll S[N_], T[N_];
 
struct ele {
    int w, x;
    ele (int w = 0, int x = 0): w(w), x(x) { }
    bool operator < (const ele &e) const { return x < e.x; }
} E[N_+N_]; int EN;
 
ll ans;
 
void solve1() {
    int x = E[EN/2].x;
    for(int i = 1; i <= EN; i++) ans += abs(x - E[i].x);
}
 
priority_queue<ll> pq1;
priority_queue<ll, vector<ll>, greater<ll> > pq2;
ll sum_pq1, sum_pq2;
 
 
int A[N_];
bool cmpA (const int &a, const int &b) {
  return S[a] + T[a] < S[b] + T[b];
}
 
void pq_ins (ll v) {
    if(!pq1.empty() && v > pq1.top()) pq2.push(v), sum_pq2 += v;
    else pq1.push(v), sum_pq1 += v;
   
    int md = (pq1.size() + pq2.size() + 1) / 2;
   
    while(pq1.size() > md) {
      sum_pq1 -= pq1.top();
      sum_pq2 += pq1.top();
      pq2.push(pq1.top());
      pq1.pop();
    }
    while(pq1.size() < md) {
      sum_pq2 -= pq2.top();
      sum_pq1 += pq2.top();
      pq1.push(pq2.top());
      pq2.pop();
    } 
}
 
ll tb1[N_];
ll tb2[N_];
 
void solve2() {
  ans = (ll)1e18;
  if(EN == 0) { ans = 0; return; }
   
  for(int i = 1; i <= N; i++) A[i] = i;
  sort(A + 1, A + N + 1, cmpA);
   
  for(int i = 1; i <= N; i++) {
    // pq1 : max heap, pq2 : min heap
    // max(pq1) < min(pq2)
     
    int x = A[i];
     
    pq_ins(S[x]);
    pq_ins(T[x]);
     
    ll m = pq1.top();
    tb1[i] = (m * pq1.size() - sum_pq1) + (sum_pq2 - m * pq2.size());
  }
   
  while(!pq1.empty()) pq1.pop(); sum_pq1 = 0;
  while(!pq2.empty()) pq2.pop(); sum_pq2 = 0;
   
  for(int i = N; i >= 1; i--) {
    // pq1 : max heap, pq2 : min heap
     
    int x = A[i];
     
    pq_ins(S[x]);
    pq_ins(T[x]);
     
    ll m = pq1.top();
    tb2[i] = (m * pq1.size() - sum_pq1) + (sum_pq2 - m * pq2.size());
  }
   
  for(int i = 1; i <= N; i++) {
    ans = min(ans, tb1[i] + tb2[i + 1]);
  }
}
 
int main() {
    int M; scanf("%d%d", &K, &M);
    for(; M--; ) {
        char p[3], q[3]; int s, t;
        scanf("%s%d%s%d", p, &s, q, &t);
 
        if(*p == *q) {
            sum_of_same_part += abs(s - t);
        }else {
            ++N;
            if(s > t) swap(s, t);
            S[N] = s; T[N] = t;
            E[++EN] = ele(-N, s);
            E[++EN] = ele(+N, t);
        }
    }
 
    sort(E+1, E+EN+1);
    E[EN+1].x = (int)2e9;
    if(K == 1) solve1();
    else solve2();
 
    printf("%lld\n", ans + sum_of_same_part + N);
 
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void pq_ins(ll)':
bridge.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pq1.size() > md) {
                      ^
bridge.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pq1.size() < md) {
                      ^
bridge.cpp: In function 'int main()':
bridge.cpp:108:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int M; scanf("%d%d", &K, &M);
                                 ^
bridge.cpp:111:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s%d%s%d", p, &s, q, &t);
                                        ^

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