제출 #14382

#제출 시각아이디문제언어결과실행 시간메모리
14382tncks0121Palembang Bridges (APIO15_bridge)C++14
22 / 100
69 ms7104 KiB
#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; }

컴파일 시 표준 에러 (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);
                                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...