oj.uz

Submission #506377

# Submission time Handle Problem Language Result Execution time Memory
506377 2022-01-12T03:01:58 Z mewnian Palembang Bridges (APIO15_bridge) C++14
63 / 100
 2000 ms 6528 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#define sze(x) (ll) x.size()
#define idx(x, a) get<x>(a)
#define LID(x) (x << 1LL)
#define RID(x) (x << 1LL) + 1LL
#define ID(x) (x + MAXN)
#define CONV(x) (x - MAXN)
#define countbit(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pi;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r)
{
    return uniform_int_distribution<ll>(l, r)(rng);
}

inline ll lcm(ll u, ll v)
{
    return u * v / __gcd(u, v);
}

const ll MAXN = 2e5 + 3;
const ll INF = 1e18;

pi a[MAXN];
ll b[MAXN];
ll k, n, m, res = 0;

ll solve(ll u, ll v)
{
    ll rt = 0;
    for (ll i = 1; i <= n; ++i)
    {
        ll mn = min(abs(a[i].fi - u) + abs(a[i].se - u) + 1, abs(a[i].fi - v) + abs(a[i].se - v) + 1);
        rt += mn;
    }
    return rt;
}

ll comp(ll x, ll y)
{
    return (x > y ? 1 : (x < y ? -1 : 0));
}

void solve1()
{
    ll x = b[m / 2];
    for (ll i = 1; i <= n; ++i)
    {
        ll rt = abs(a[i].fi - x) + abs(a[i].se - x) + 1;
        res += rt;
    }
    cout << res;
}

void solve2()
{
    ll rt = INF;
    ll l = 1, r = 2, curans = INF;
    vector<ll> cl(m + 2);
    vector<ll> cr(m + 2);
    while (r <= m)
    {
        ll tans = solve(b[l], b[r]);
        if (tans <= curans)
        {
            curans = tans;
            ++r;
        }
        else
        {
            cl[l] = r - 1;
            ++l;
            if (l < r - 1) curans = solve(b[l], b[r - 1]);
            else curans = INF;
        }
    }
    for (ll i = 1; i < m; ++i) if (cl[i] == 0) cl[i] = m;
    for (ll i = 1; i < m; ++i) rt = min(rt, solve(b[i], b[cl[i]]));
    if (rt != INF) res += rt;
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OFFLINE
    freopen("input.inp", "r", stdin);
    #endif
    ll _;
    cin >> k >> _;
    n = 0, m = 0;
    ll mn = INF, mx = -INF;
    for (ll i = 1; i <= _; ++i)
    {
        char c1, c2; ll p1, p2; cin >> c1 >> p1 >> c2 >> p2;
//        c1 = 'A', c2 = 'B';
//        p1 = rand(1, _), p2 = rand(1, _);
//        cerr << c1 << " " << p1 << " " << c2 << " " << p2 << endl;
        if (c1 == c2) res += abs(p1 - p2);
        else
        {
            b[++m] = p1, b[++m] = p2;
            a[++n] = {p1, p2};
        }
    }
    b[m + 1] = 1e12;
    sort(b + 1, b + m + 1);
    if (k == 1) solve1();
    else solve2();
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:109:8: warning: unused variable 'mn' [-Wunused-variable]
  109 |     ll mn = INF, mx = -INF;
      |        ^~
bridge.cpp:109:18: warning: unused variable 'mx' [-Wunused-variable]
  109 |     ll mn = INF, mx = -INF;
      |                  ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 17 ms 3388 KB Output is correct
13 Correct 38 ms 3404 KB Output is correct
14 Correct 26 ms 3020 KB Output is correct
15 Correct 22 ms 2088 KB Output is correct
16 Correct 24 ms 3372 KB Output is correct
17 Correct 29 ms 3460 KB Output is correct
18 Correct 32 ms 3452 KB Output is correct
19 Correct 36 ms 3404 KB Output is correct
20 Correct 24 ms 3396 KB Output is correct
21 Correct 34 ms 3436 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 12 ms 332 KB Output is correct
14 Correct 23 ms 332 KB Output is correct
15 Correct 24 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 7 ms 364 KB Output is correct
18 Correct 4 ms 332 KB Output is correct
19 Correct 14 ms 332 KB Output is correct
20 Correct 26 ms 332 KB Output is correct
21 Correct 19 ms 388 KB Output is correct
22 Correct 24 ms 368 KB Output is correct
23 Correct 17 ms 392 KB Output is correct
24 Correct 24 ms 332 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 14 ms 388 KB Output is correct
14 Correct 24 ms 332 KB Output is correct
15 Correct 24 ms 392 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 8 ms 332 KB Output is correct
18 Correct 4 ms 332 KB Output is correct
19 Correct 15 ms 332 KB Output is correct
20 Correct 24 ms 392 KB Output is correct
21 Correct 19 ms 392 KB Output is correct
22 Correct 26 ms 332 KB Output is correct
23 Correct 17 ms 332 KB Output is correct
24 Correct 27 ms 332 KB Output is correct
25 Execution timed out 2071 ms 6528 KB Time limit exceeded
26 Halted 0 ms 0 KB -