Submission #886266

#	Time	Username	Problem	Language	Result	Execution time	Memory
886266		tsumondai	Palembang Bridges (APIO15_bridge)	C++14	Compilation error	0 ms	0 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 100005
#define pb push_back
#define all(v) (v).begin(), (v).end()
typedef long long lld;
 
int K, N, M;
lld D[MAXN], E[MAXN];
 
struct Z{
    int a, b;
} A[MAXN];
 
void proc(lld V[])
{
    if (!N) return;
    lld val = abs(A[1].a - A[1].b);
    priority_queue <int> p, q;
    int mid = A[1].a;
    if (A[1].b < mid) p.push(A[1].b);
    else q.push(-A[1].b);
    V[1] = val;
    for (int i=2;i<=N;i++){
        val += abs(mid - A[i].a) + abs(mid - A[i].b);
        if (A[i].a < mid) p.push(A[i].a);
        else q.push(-A[i].a);
        if (A[i].b < mid) p.push(A[i].b);
        else q.push(-A[i].b);
        while (sz(p) < sz(q)){
            int nxt = -q.top(); q.pop();
            p.push(mid);
            val += (lld)(nxt - mid) * sz(p) - (lld)(nxt - mid) * (sz(q) + 1);
            mid = nxt;
        }
        while (sz(p) > sz(q)+1){
            int nxt = p.top(); p.pop();
            q.push(-mid);
            val += (lld)(mid - nxt) * sz(q) - (lld)(mid - nxt) * (sz(p) + 1);
            mid = nxt;
        }
        V[i] = val;
    }
}
 
int main()
{
    scanf("%d%d", &K, &M);
    vector <int> arr;
    lld def = 0;
    while (M--){
        char p, q; int a, b;
        scanf(" %c%d %c%d", &p, &a, &q, &b);
        if (p == q){ def += abs(a-b); continue; }
        A[++N] = {a, b};
    }
    sort(A+1, A+N+1, [](const Z &a, const Z &b){
        return a.a+a.b < b.a+b.b;
    });
    proc(D);
    if (K == 1){ printf("%lld\n", D[N] + def + N); return 0; }
    reverse(A+1, A+N+1);
    proc(E);
    lld ans = 1e18;
    for (int i=0;i<=N;i++) ans = min(ans, def + D[i] + E[N-i] + N);
    printf("%lld\n", ans);
}

Compilation message (stderr)

bridge.cpp: In function 'void proc(lld*)':
bridge.cpp:32:16: error: 'sz' was not declared in this scope
   32 |         while (sz(p) < sz(q)){
      |                ^~
bridge.cpp:38:16: error: 'sz' was not declared in this scope
   38 |         while (sz(p) > sz(q)+1){
      |                ^~
bridge.cpp: In function 'int main()':
bridge.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d%d", &K, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
bridge.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf(" %c%d %c%d", &p, &a, &q, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~