Submission #100575

#	Time	Username	Problem	Language	Result	Execution time	Memory
100575		Extazy	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	69 ms	3784 KiB

bridge

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 200007;

int n, k, arr[N], sz;
long long ans, offset;

long long it1[N], it2[N];

long long ps[N];

long long get_sum(int l, int r) {
  return ps[r] - ps[l - 1];
}

void update(long long *it, int pos, int val) {
  for(;pos<=sz;pos+=pos&(-pos)) it[pos] += val;
}

long long query(long long *it, int pos) {
  long long ans = 0;

  for(;pos>=1;pos-=pos&(-pos)) ans += it[pos];

  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i, x, y;
  char tmp1[4], tmp2[4];

  scanf("%d %d", &k, &n);

  for(i=1;i<=n;i++) {
    scanf("%s %d %s %d", tmp1, &x, tmp2, &y);

    if(tmp1[0]==tmp2[0]) offset += abs(x - y);
    else {
      arr[++sz] = x;
      arr[++sz] = y;
      
      ++offset;
    }
  }

  sort(arr + 1, arr + 1 + sz);

  for(i=1;i<=sz;i++) {
    ps[i] = ps[i - 1] + arr[i];
  }

  ans = offset;

  for(i=1;i<=sz;i++) {
    ans += abs(arr[i] - arr[(sz + 1) / 2]);
  }

  if(k==2) {
    for(i=1;i<sz;i++) {
      int mid1 = (i + 1) / 2, mid2 = (i + 1 + sz) / 2, sz1 = mid1, sz2 = i - mid1, sz3 = mid2 - i, sz4 = sz - mid2;

      if(i%2==0) ++mid1;

      ans = min(ans, offset + (sz1 + sz4)*1ll*(arr[mid2] - arr[mid1]) + (arr[mid1]*1ll*sz1 - get_sum(1, mid1)) + (get_sum(mid1 + 1, i) - arr[mid1]*1ll*sz2) + (arr[mid2]*1ll*sz3 - get_sum(i + 1, mid2)) + (get_sum(mid2 + 1, sz) - arr[mid2]*1ll*sz4));
    }
  }

  printf("%lld\n", ans);

  return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &k, &n);
   ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s %d %s %d", tmp1, &x, tmp2, &y);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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