Submission #41484

#	Time	Username	Problem	Language	Result	Execution time	Memory
41484		Nurlykhan	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	120 ms	1664 KiB

bridge

    #include <bits/stdc++.h>
     
    #define pii pair<int, int>
    #define f first
    #define s second
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define ld long double
    #define sz(v) int(v.size())
    #define all(v) v.begin(), v.end()
    #define vec vector<int>
    #define dead not_bad
    #define bad gooood
     
    #define left not_right
    #define y1 what
     
    using namespace std;
     
    const int N = (int) 2e5 + 10;
    const int M = (int) 2e6;
    const ll LINF = (ll) 2e18;
    const int INF = (int) 1e9 + 7;
    const int ALPHA = 26;
    const int mod = INF;
    const double PI = 3.14159265359;
    const ld EPS = (ld) 1e-12;
     
    const int nx[4] = {0, 0, -1, 1};
    const int ny[4] = {1, -1, 0, 0};
     
    vector<int> a, b;
    int k, n;
     
    inline ll get1(int x1, int x2) {
        ll cur = 0;
        for (int i = 0; i < sz(a); i++) {
          int val1, val2;
          if (a[i] <= x1 && x1 <= b[i]) {
            val1 = b[i] - a[i];
          } else if (a[i] > x1) {
            val1 = a[i] + b[i] - 2 * x1;
          } else {
            val1 = 2 * x1 - (a[i] + b[i]);
          }
          if (a[i] <= x2 && x2 <= b[i]) {
            val2 = b[i] - a[i];
          } else if (a[i] > x2) {
            val2 = a[i] + b[i] - 2 * x2;
          } else {
            val2 = 2 * x2 - (a[i] + b[i]);
          }
          cur += min(val1, val2);
        }
        return cur;
    }
     
    ll get(ll x) {
      ll cur = 0;
        for (int i = 0; i < sz(a); i++) {
          if (a[i] <= x && x <= b[i]) {
            cur += b[i] - a[i];
          } else if (a[i] > x) {
            cur += a[i] + b[i] - 2 * x;
          } else if (b[i] < x) {
            cur += 2 * x - (a[i] + b[i]);
          } else {
            assert(0);
          }
        }
        if (k == 2) {
          int l = 0, r = INF;
          while (r - l > 2) {
            int m = (l + r) / 2;
            if (get1(m, x) > get1(m + 1, x)) {
              l = m;
            } else {
              r = m;
            }
          }
          for (ll i = l; i <= r; i++) 
            cur = min(cur, get1(i, x));
        }
        return cur;
    }
     
    ll solve() {
      int l = 0, r = INF;
          while (r - l > 100) {
            int m = (l + r) / 2;
            if (get(m) > get(m + 1)) {
              l = m;
            } else {
              r = m;
            }
          }
      ll ans = LINF;
      for (ll i = l; i <= r; i++) {
        ans = min(ans, get(i));
      }
      return ans + sz(a);
    }
     
    int main() {
      #define fn "teams"
      #ifdef witch
          freopen("input.txt", "r", stdin);
          freopen("output.txt", "w", stdout);
      #else
          //freopen(fn".in", "r", stdin);
          //freopen(fn".out", "w", stdout);
      #endif  
      ll ans = 0;
      cin >> k >> n;
      for (int i = 1; i <= n; i++) {
        char ta, tb;
        int x1, x2;
        scanf("\n%c %d %c %d", &ta, &x1, &tb, &x2);
        //cout << ta << ' ' << x1 << ' ' << tb << ' ' << x2 << endl;
        if (x1 > x2) 
          swap(x1, x2);
        if (ta == tb) {
          ans += x2 - x1;
        } else {
          a.pb(x1);
          b.pb(x2);
        }
      }
      cout << ans + solve();
      return 0;
    }

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:119:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c %d %c %d", &ta, &x1, &tb, &x2);
                                                   ^

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