답안 #41400 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41400	2018-02-17T06:57:38 Z	Nurlykhan	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2000 ms	3616 KB

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<ll> a, b;
int k, n;

ll get1(ll x1, ll x2) {
    ll cur = 0;
    for (int i = 0; i < sz(a); i++) {
      ll 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) {
      ll l = 0, r = INF;
      while (r - l > 2) {
        ll m1 = l + (r - l) / 3;
        ll m2 = r - (r - l) / 3;
        if (get1(m1, x) > get1(m2, x)) {
          l = m1;
        } else {
          r = m2;
        }
      }
      for (ll i = l; i <= r; i++) cur = min(cur, get1(i, x));
    }
    return cur;
}

ll solve() {
  ll l = 0, r = INF;
  while (r - l > 2) {
    ll m1 = l + (r - l) / 3;
    ll m2 = r - (r - l) / 3;
    if (get(m1) > get(m2)) {
      l = m1;
    } else {
      r = m2;
    }
  }
  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;
    ll x1, x2;
    cin >> 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;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	2 ms	552 KB	Output is correct
4	Correct	2 ms	572 KB	Output is correct
5	Correct	3 ms	572 KB	Output is correct
6	Correct	2 ms	572 KB	Output is correct
7	Correct	3 ms	572 KB	Output is correct
8	Correct	2 ms	680 KB	Output is correct
9	Correct	3 ms	680 KB	Output is correct
10	Correct	3 ms	680 KB	Output is correct
11	Correct	3 ms	680 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	680 KB	Output is correct
2	Correct	1 ms	680 KB	Output is correct
3	Correct	2 ms	680 KB	Output is correct
4	Correct	2 ms	680 KB	Output is correct
5	Correct	3 ms	680 KB	Output is correct
6	Correct	2 ms	680 KB	Output is correct
7	Correct	4 ms	680 KB	Output is correct
8	Correct	2 ms	680 KB	Output is correct
9	Correct	3 ms	680 KB	Output is correct
10	Correct	2 ms	740 KB	Output is correct
11	Correct	3 ms	740 KB	Output is correct
12	Correct	75 ms	2432 KB	Output is correct
13	Correct	211 ms	2432 KB	Output is correct
14	Correct	121 ms	2432 KB	Output is correct
15	Correct	109 ms	2432 KB	Output is correct
16	Correct	102 ms	2432 KB	Output is correct
17	Correct	125 ms	2432 KB	Output is correct
18	Correct	110 ms	2432 KB	Output is correct
19	Correct	169 ms	2628 KB	Output is correct
20	Correct	146 ms	2628 KB	Output is correct
21	Correct	160 ms	2628 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2628 KB	Output is correct
2	Correct	1 ms	2628 KB	Output is correct
3	Correct	4 ms	2628 KB	Output is correct
4	Correct	4 ms	2628 KB	Output is correct
5	Correct	3 ms	2628 KB	Output is correct
6	Correct	2 ms	2628 KB	Output is correct
7	Correct	4 ms	2628 KB	Output is correct
8	Correct	5 ms	2628 KB	Output is correct
9	Correct	5 ms	2628 KB	Output is correct
10	Correct	4 ms	2628 KB	Output is correct
11	Correct	4 ms	2628 KB	Output is correct
12	Correct	4 ms	2628 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2628 KB	Output is correct
2	Correct	2 ms	2628 KB	Output is correct
3	Correct	4 ms	2628 KB	Output is correct
4	Correct	4 ms	2628 KB	Output is correct
5	Correct	3 ms	2628 KB	Output is correct
6	Correct	2 ms	2628 KB	Output is correct
7	Correct	3 ms	2628 KB	Output is correct
8	Correct	4 ms	2628 KB	Output is correct
9	Correct	5 ms	2628 KB	Output is correct
10	Correct	4 ms	2628 KB	Output is correct
11	Correct	4 ms	2628 KB	Output is correct
12	Correct	4 ms	2628 KB	Output is correct
13	Correct	28 ms	2628 KB	Output is correct
14	Correct	35 ms	2628 KB	Output is correct
15	Correct	47 ms	2628 KB	Output is correct
16	Correct	10 ms	2628 KB	Output is correct
17	Correct	19 ms	2628 KB	Output is correct
18	Correct	14 ms	2628 KB	Output is correct
19	Correct	34 ms	2628 KB	Output is correct
20	Correct	36 ms	2628 KB	Output is correct
21	Correct	23 ms	2628 KB	Output is correct
22	Correct	32 ms	2628 KB	Output is correct
23	Correct	29 ms	2628 KB	Output is correct
24	Correct	28 ms	2628 KB	Output is correct

Subtask #5
0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2628 KB	Output is correct
2	Correct	1 ms	2628 KB	Output is correct
3	Correct	4 ms	2628 KB	Output is correct
4	Correct	4 ms	2628 KB	Output is correct
5	Correct	3 ms	2628 KB	Output is correct
6	Correct	2 ms	2628 KB	Output is correct
7	Correct	5 ms	2628 KB	Output is correct
8	Correct	4 ms	2628 KB	Output is correct
9	Correct	4 ms	2628 KB	Output is correct
10	Correct	4 ms	2628 KB	Output is correct
11	Correct	4 ms	2628 KB	Output is correct
12	Correct	4 ms	2628 KB	Output is correct
13	Correct	28 ms	2628 KB	Output is correct
14	Correct	35 ms	2628 KB	Output is correct
15	Correct	38 ms	2628 KB	Output is correct
16	Correct	10 ms	2628 KB	Output is correct
17	Correct	18 ms	2628 KB	Output is correct
18	Correct	21 ms	2628 KB	Output is correct
19	Correct	21 ms	2628 KB	Output is correct
20	Correct	25 ms	2628 KB	Output is correct
21	Correct	25 ms	2628 KB	Output is correct
22	Correct	30 ms	2628 KB	Output is correct
23	Correct	36 ms	2628 KB	Output is correct
24	Correct	27 ms	2628 KB	Output is correct
25	Execution timed out	2039 ms	3616 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

답안 #41400

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
0 / 37.0