답안 #46626 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46626	2018-04-22T12:02:36 Z	tieunhi	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	350 ms	51216 KB

bridge

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 100005
#define maxc 1000000000000000007ll

using namespace std;

int k, n, rr[2*N];
pii a[N];
long long f[2][N];

struct IntervalTree
{
    long long t[N << 3];
    int sz[N << 3];

    void build(int l, int r, int id)
    {
        t[id] = sz[id] = 0;
        if (l == r) return;
        int mid = (r + l)/2;
        build(l, mid, id*2);
        build(mid+1, r, id*2+1);
    }
    void update(int l, int r, int id, int x, int val)
    {
        if (l == r)
        {
            t[id] += val;
            sz[id]++;
            return;
        }
        int mid = (r + l)/2;
        if (x <= mid) update(l, mid, id*2, x, val);
        else update(mid+1, r, id*2+1, x, val);
        t[id] += val;
        sz[id]++;
    }
    int getpos(int l, int r, int id, int x)
    {
        if (l == r) return l;
        int mid = (r + l)/2;
        if (sz[id*2] >= x) return getpos(l, mid, id*2, x);
        return getpos(mid+1, r, id*2+1, x-sz[id*2]);
    }
    long long get(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return 0;
        if (l >= x && r <= y) return t[id];
        int mid = (r + l)/2;
        long long a = get(l, mid, id*2, x, y);
        long long b = get(mid+1, r, id*2+1, x, y);
        return a + b;
    }
    int getSz(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return 0;
        if (l >= x && r <= y) return sz[id];
        int mid = (r + l)/2;
        int a = getSz(l, mid, id*2, x, y);
        int b = getSz(mid+1, r, id*2+1, x, y);
        return a + b;
    }
}t;

bool cmp(pii x, pii y)
{
    return x.F + x.S < y.F + y.S;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("INP.TXT", "r", stdin);
    //freopen("BRIDGE.INP", "r", stdin);
    //freopen("BRIDGE.OUT", "w", stdout);
    cin >> k >> n;
    int cur = 0;
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        char x, y; int u, v;
        cin >> x >> u >> y >> v;
        if (x == y) ans += abs(u-v);
        else {
            if (u > v) swap(u, v);
            a[++cur] = mp(u, v);
        }
    }
    n = cur;
    if (n == 0)
    {
        cout <<ans;
        return 0;
    }
    sort(a+1, a+n+ 1, cmp);
    cur = 0;
    for (int i = 1; i <= n; i++)
    {
        rr[++cur] = a[i].F;
        rr[++cur] = a[i].S;
    }
    sort(rr+1, rr+cur+1);
    cur = unique(rr+1, rr+cur+1) - rr - 1;
    for (int i = 1; i <= n; i++)
    {
        a[i].F = lower_bound(rr+1, rr+cur+1, a[i].F) - rr;
        a[i].S = lower_bound(rr+1, rr+cur+1, a[i].S) - rr;
    }
    for (int i = 1; i <= n; i++)
    {
        t.update(1, 2*n, 1, a[i].F, rr[a[i].F]);
        t.update(1, 2*n, 1, a[i].S, rr[a[i].S]);

        int pos = t.getpos(1, 2*n, 1, i);
        long long xx = t.get(1, 2*n, 1, pos+1, 2*n) - 1ll*rr[pos]*t.getSz(1, 2*n, 1, pos+1, 2*n);
        long long yy = 1ll*rr[pos]*t.getSz(1, 2*n, 1, 1, pos-1) - t.get(1, 2*n, 1, 1, pos-1);
        f[0][i] = xx + yy;
    }
    t.build(1, 2*n, 1);
    for (int i = n; i >= 1; i--)
    {
        t.update(1, 2*n, 1, a[i].F, rr[a[i].F]);
        t.update(1, 2*n, 1, a[i].S, rr[a[i].S]);

        int pos = t.getpos(1, 2*n, 1, (n-i+1));
        long long xx = t.get(1, 2*n, 1, pos+1, 2*n) - 1ll*rr[pos]*t.getSz(1, 2*n, 1, pos+1, 2*n);
        long long yy = 1ll*rr[pos]*t.getSz(1, 2*n, 1, 1, pos-1) - t.get(1, 2*n, 1, 1, pos-1);
        f[1][i] = xx + yy;
    }
    if (k == 1) cout <<f[0][n] + ans + n;
    else
    {
        long long res = maxc;
        for (int i = 0; i <= n; i++)
            res = min(res, ans + f[0][i] + f[1][i+1] + n);
        cout <<res;
    }
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	3 ms	540 KB	Output is correct
4	Correct	5 ms	624 KB	Output is correct
5	Correct	4 ms	736 KB	Output is correct
6	Correct	3 ms	776 KB	Output is correct
7	Correct	4 ms	796 KB	Output is correct
8	Correct	3 ms	820 KB	Output is correct
9	Correct	4 ms	840 KB	Output is correct
10	Correct	4 ms	972 KB	Output is correct
11	Correct	4 ms	972 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	972 KB	Output is correct
2	Correct	2 ms	972 KB	Output is correct
3	Correct	3 ms	984 KB	Output is correct
4	Correct	4 ms	992 KB	Output is correct
5	Correct	4 ms	1012 KB	Output is correct
6	Correct	3 ms	1012 KB	Output is correct
7	Correct	4 ms	1076 KB	Output is correct
8	Correct	3 ms	1100 KB	Output is correct
9	Correct	5 ms	1120 KB	Output is correct
10	Correct	3 ms	1144 KB	Output is correct
11	Correct	4 ms	1164 KB	Output is correct
12	Correct	153 ms	11108 KB	Output is correct
13	Correct	334 ms	13476 KB	Output is correct
14	Correct	204 ms	14408 KB	Output is correct
15	Correct	222 ms	14408 KB	Output is correct
16	Correct	143 ms	17612 KB	Output is correct
17	Correct	261 ms	19956 KB	Output is correct
18	Correct	169 ms	21960 KB	Output is correct
19	Correct	282 ms	24292 KB	Output is correct
20	Correct	170 ms	26168 KB	Output is correct
21	Correct	248 ms	28316 KB	Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	28316 KB	Output is correct
2	Correct	2 ms	28316 KB	Output is correct
3	Correct	2 ms	28316 KB	Output is correct
4	Correct	2 ms	28316 KB	Output is correct
5	Correct	2 ms	28316 KB	Output is correct
6	Correct	2 ms	28316 KB	Output is correct
7	Correct	2 ms	28316 KB	Output is correct
8	Correct	2 ms	28316 KB	Output is correct
9	Correct	2 ms	28316 KB	Output is correct
10	Correct	2 ms	28316 KB	Output is correct
11	Correct	2 ms	28316 KB	Output is correct
12	Correct	2 ms	28316 KB	Output is correct
13	Correct	3 ms	28316 KB	Output is correct
14	Correct	3 ms	28316 KB	Output is correct
15	Correct	4 ms	28316 KB	Output is correct
16	Correct	2 ms	28316 KB	Output is correct
17	Correct	3 ms	28316 KB	Output is correct
18	Correct	3 ms	28316 KB	Output is correct
19	Correct	3 ms	28316 KB	Output is correct
20	Correct	4 ms	28316 KB	Output is correct
21	Correct	3 ms	28316 KB	Output is correct
22	Correct	4 ms	28316 KB	Output is correct
23	Correct	3 ms	28316 KB	Output is correct
24	Correct	4 ms	28316 KB	Output is correct
25	Correct	151 ms	29556 KB	Output is correct
26	Correct	179 ms	30596 KB	Output is correct
27	Correct	347 ms	32324 KB	Output is correct
28	Correct	341 ms	34736 KB	Output is correct
29	Correct	350 ms	37112 KB	Output is correct
30	Correct	158 ms	37112 KB	Output is correct
31	Correct	138 ms	39848 KB	Output is correct
32	Correct	260 ms	42296 KB	Output is correct
33	Correct	188 ms	44108 KB	Output is correct
34	Correct	273 ms	46440 KB	Output is correct
35	Correct	197 ms	48416 KB	Output is correct
36	Correct	275 ms	50508 KB	Output is correct
37	Correct	141 ms	51216 KB	Output is correct

답안 #46626

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 37.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
37.0 / 37.0