Submission #14382

#	Time	Username	Problem	Language	Result	Execution time	Memory
14382		tncks0121	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	69 ms	7104 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[a]] + T[A[a]] < S[A[b]] + T[A[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
    
    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:107: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:110: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: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37