oj.uz

Submission #170971

# Submission time Handle Problem Language Result Execution time Memory
170971 2019-12-26T20:10:48 Z ne4eHbKa Palembang Bridges (APIO15_bridge) C++17
31 / 100
 2000 ms 3704 KB 
//{ <defines>
#ifndef _LOCAL
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#endif

#include <bits/stdc++.h>
using namespace std;

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int(x.size())
#define pw(x) (1 << (x))
#define PW(x) (1ll << (x))
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset(x, y, sizeof x)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;

const int oo = 2e9;
const ll OO = 4e18;
//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int md = 0x3b800001;
const int MD = 1e9 + 7;

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}
//} </defines>
const int N = 1e5 + 5;

int n, m;
ll pl[N], pr[N], l[N], r[N];
ll constant;

ll all_to(ll x, ll *a, ll *p) {
    int t = lower_bound(a, a + m, x) - a;
    re (t ? x * t - p[t - 1] : 0) +
       (p[m - 1] - (t ? p[t - 1] : 0) - x * (m - t));
}

ll all_to(ll x) {
    re all_to(x, r, pr) + all_to(x, l, pl);
}

ll solve1() {
    ifn(m) re 0;
    sort(l, l + m); partial_sum(l, l + m, pl);
    sort(r, r + m); partial_sum(r, r + m, pr);
    ll ans = OO;
    fo(m) umin(ans, all_to(l[i]));
    fo(m) umin(ans, all_to(r[i]));
    re ans + m;
}

ll get(ll x0, ll x1) {
    ll ans = 0;
    fo(m) ans += min(abs(l[i] - x0) + abs(r[i] - x0),
                     abs(l[i] - x1) + abs(r[i] - x1));
    re ans;
}

ll solve2() {
    ifn(m) re 0;
    vi x; fo(m) x.pb(l[i]), x.pb(r[i]);
    ll ans = OO;
    fo(sz(x)) fr(j, i + 1) umin(ans, get(x[i], x[j]));
    re ans + m;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int tp;
    cin >> tp >> n;
    fo(n) {
        char a, b;
        int x, y;
        cin >> a >> x >> b >> y;
        if(x > y) swap(x, y);
        if(a == b) constant += y - x;
        else l[m] = x, r[m] = y, m++;
    }
    cout << constant + (tp & 1 ? solve1() : solve2()) << endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 4 ms 312 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 4 ms 380 KB Output is correct
12 Correct 99 ms 3508 KB Output is correct
13 Correct 220 ms 3576 KB Output is correct
14 Correct 136 ms 3192 KB Output is correct
15 Correct 129 ms 2208 KB Output is correct
16 Correct 150 ms 3448 KB Output is correct
17 Correct 210 ms 3704 KB Output is correct
18 Correct 178 ms 3524 KB Output is correct
19 Correct 221 ms 3448 KB Output is correct
20 Correct 169 ms 3472 KB Output is correct
21 Correct 205 ms 3448 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 9 ms 376 KB Output is correct
8 Correct 9 ms 376 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 9 ms 380 KB Output is correct
11 Correct 9 ms 376 KB Output is correct
12 Correct 9 ms 376 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 9 ms 380 KB Output is correct
8 Correct 9 ms 376 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 9 ms 376 KB Output is correct
11 Correct 9 ms 376 KB Output is correct
12 Correct 9 ms 376 KB Output is correct
13 Execution timed out 2071 ms 376 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 9 ms 376 KB Output is correct
8 Correct 9 ms 376 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 9 ms 376 KB Output is correct
11 Correct 9 ms 376 KB Output is correct
12 Correct 9 ms 408 KB Output is correct
13 Execution timed out 2078 ms 376 KB Time limit exceeded
14 Halted 0 ms 0 KB -