답안 #78801 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78801	2018-10-09T01:32:30 Z	wleung_bvg	자리 배치 (IOI18_seats)	C++14	100 / 100	2924 ms	48188 KB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(),(a).end()
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(auto i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
#define FORE(i,a) for(auto&&i:a)
#define sz(a) (int((a).size()))
#define MIN(a,b) ((a)=min((a),(b)))
#define MAX(a,b) ((a)=max((a),(b)))
using ll=long long;using ld=long double;using uint=unsigned int;using ull=unsigned long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pill=pair<int,ll>;using plli=pair<ll,int>;using pdd=pair<double,double>;using pld=pair<ld,ld>;
constexpr const char nl='\n',sp=' ';constexpr const int INT_INF=0x3f3f3f3f;constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF=numeric_limits<double>::infinity();constexpr const ld LD_INF=numeric_limits<ld>::infinity();constexpr const double EPS=1e-9;

const int MAXHW = 1e6 + 5;

int H, W, N, M, VAL[MAXHW], L[MAXHW], R[MAXHW], C[MAXHW], temp[4];
pii T[MAXHW * 2];

pii merge(const pii &l, const pii &r) {
    if (l.f < r.f) return l;
    else if (l.f > r.f) return r;
    else return mp(l.f, l.s + r.s);
}

void apply(int i, int v) {
    T[i].f += v;
    if (i < N) L[i] += v;
}

void pushup(int i) {
    while (i > 1) {
        i >>= 1;
        T[i] = merge(T[i << 1], T[i << 1 | 1]);
        T[i].f += L[i];
    }
}

void propagate(int i) {
    for (int h = M; h > 0; h--) {
        int ii = i >> h;
        if (L[ii] != 0) {
            apply(ii << 1, L[ii]);
            apply(ii << 1 | 1, L[ii]);
            L[ii] = 0;
        }
    }
}

void update(int l, int r, int v) {
    int l0 = l += N, r0 = r += N;
    propagate(l);
    propagate(r);
    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) apply(l++, v);
        if (!(r & 1)) apply(r--, v);
    }
    pushup(l0);
    pushup(r0);
}

int getVal(int r, int c) {
    return r < 0 || r >= H || c < 0 || c >= W ? N : VAL[r * W + c];
}

void updateSingle(int r, int c, int v) {
    FOR(i, 2) FOR(j, 2) temp[i * 2 + j] = getVal(r - i, c - j);
    sort(temp, temp + 4);
    if (temp[0] < temp[1]) update(temp[0], temp[1] - 1, v);
    if (temp[2] < temp[3]) update(temp[2], temp[3] - 1, v);
}

void updateSquare(int r, int c, int v) {
    FOR(i, 2) FOR(j, 2) updateSingle(r + i, c + j, -1);
    VAL[r * W + c] = v;
    FOR(i, 2) FOR(j, 2) updateSingle(r + i, c + j, 1);
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
    N = (H = h) * (W = w);
    M = 0;
    for (int i = 1; i <= N; M++) i <<= 1;
    FOR(i, N) {
        T[N + i] = mp(0, 1);
        L[i] = 0;
    }
    Rev(i, N - 1, 0) T[i] = merge(T[i << 1], T[i << 1 | 1]);
    FOR(i, N) VAL[(R[i] = r[i]) * W + (C[i] = c[i])] = i;
    FOR(i, H + 1) FOR(j, W + 1) updateSingle(i, j, 1);
    assert(T[1].f == 4);
}

int swap_seats(int a, int b) {
    updateSquare(R[a], C[a], b);
    updateSquare(R[b], C[b], a);
    swap(R[a], R[b]);
    swap(C[a], C[b]);
    assert(T[1].f == 4);
    return T[1].s;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	504 KB	Output is correct
2	Correct	36 ms	584 KB	Output is correct
3	Correct	38 ms	584 KB	Output is correct
4	Correct	20 ms	676 KB	Output is correct
5	Correct	20 ms	676 KB	Output is correct
6	Correct	28 ms	676 KB	Output is correct
7	Correct	32 ms	732 KB	Output is correct
8	Correct	30 ms	740 KB	Output is correct
9	Correct	30 ms	756 KB	Output is correct
10	Correct	33 ms	888 KB	Output is correct
11	Correct	29 ms	888 KB	Output is correct
12	Correct	19 ms	888 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	504 KB	Output is correct
2	Correct	36 ms	584 KB	Output is correct
3	Correct	38 ms	584 KB	Output is correct
4	Correct	20 ms	676 KB	Output is correct
5	Correct	20 ms	676 KB	Output is correct
6	Correct	28 ms	676 KB	Output is correct
7	Correct	32 ms	732 KB	Output is correct
8	Correct	30 ms	740 KB	Output is correct
9	Correct	30 ms	756 KB	Output is correct
10	Correct	33 ms	888 KB	Output is correct
11	Correct	29 ms	888 KB	Output is correct
12	Correct	19 ms	888 KB	Output is correct
13	Correct	68 ms	1156 KB	Output is correct
14	Correct	75 ms	1284 KB	Output is correct
15	Correct	40 ms	1284 KB	Output is correct
16	Correct	37 ms	1284 KB	Output is correct
17	Correct	51 ms	1284 KB	Output is correct
18	Correct	61 ms	1284 KB	Output is correct
19	Correct	60 ms	1284 KB	Output is correct
20	Correct	50 ms	1284 KB	Output is correct
21	Correct	39 ms	1324 KB	Output is correct
22	Correct	36 ms	1324 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1933 ms	47804 KB	Output is correct
2	Correct	1215 ms	47808 KB	Output is correct
3	Correct	1179 ms	47808 KB	Output is correct
4	Correct	957 ms	47808 KB	Output is correct
5	Correct	1028 ms	47808 KB	Output is correct
6	Correct	1157 ms	47808 KB	Output is correct
7	Correct	1135 ms	47808 KB	Output is correct
8	Correct	1116 ms	47808 KB	Output is correct
9	Correct	1143 ms	47808 KB	Output is correct
10	Correct	1198 ms	47808 KB	Output is correct

Subtask #4
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	47808 KB	Output is correct
2	Correct	160 ms	47808 KB	Output is correct
3	Correct	1059 ms	47808 KB	Output is correct
4	Correct	1886 ms	47808 KB	Output is correct
5	Correct	1059 ms	47808 KB	Output is correct
6	Correct	1701 ms	47808 KB	Output is correct
7	Correct	959 ms	47808 KB	Output is correct
8	Correct	1137 ms	47808 KB	Output is correct
9	Correct	1110 ms	47808 KB	Output is correct
10	Correct	1118 ms	47808 KB	Output is correct
11	Correct	1097 ms	47808 KB	Output is correct

Subtask #5
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	47808 KB	Output is correct
2	Correct	127 ms	47808 KB	Output is correct
3	Correct	173 ms	47808 KB	Output is correct
4	Correct	218 ms	47808 KB	Output is correct
5	Correct	354 ms	47808 KB	Output is correct
6	Correct	1459 ms	48060 KB	Output is correct
7	Correct	1630 ms	48060 KB	Output is correct
8	Correct	1414 ms	48060 KB	Output is correct
9	Correct	2394 ms	48064 KB	Output is correct
10	Correct	1401 ms	48064 KB	Output is correct
11	Correct	1448 ms	48064 KB	Output is correct
12	Correct	1405 ms	48064 KB	Output is correct

Subtask #6
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	504 KB	Output is correct
2	Correct	36 ms	584 KB	Output is correct
3	Correct	38 ms	584 KB	Output is correct
4	Correct	20 ms	676 KB	Output is correct
5	Correct	20 ms	676 KB	Output is correct
6	Correct	28 ms	676 KB	Output is correct
7	Correct	32 ms	732 KB	Output is correct
8	Correct	30 ms	740 KB	Output is correct
9	Correct	30 ms	756 KB	Output is correct
10	Correct	33 ms	888 KB	Output is correct
11	Correct	29 ms	888 KB	Output is correct
12	Correct	19 ms	888 KB	Output is correct
13	Correct	68 ms	1156 KB	Output is correct
14	Correct	75 ms	1284 KB	Output is correct
15	Correct	40 ms	1284 KB	Output is correct
16	Correct	37 ms	1284 KB	Output is correct
17	Correct	51 ms	1284 KB	Output is correct
18	Correct	61 ms	1284 KB	Output is correct
19	Correct	60 ms	1284 KB	Output is correct
20	Correct	50 ms	1284 KB	Output is correct
21	Correct	39 ms	1324 KB	Output is correct
22	Correct	36 ms	1324 KB	Output is correct
23	Correct	1933 ms	47804 KB	Output is correct
24	Correct	1215 ms	47808 KB	Output is correct
25	Correct	1179 ms	47808 KB	Output is correct
26	Correct	957 ms	47808 KB	Output is correct
27	Correct	1028 ms	47808 KB	Output is correct
28	Correct	1157 ms	47808 KB	Output is correct
29	Correct	1135 ms	47808 KB	Output is correct
30	Correct	1116 ms	47808 KB	Output is correct
31	Correct	1143 ms	47808 KB	Output is correct
32	Correct	1198 ms	47808 KB	Output is correct
33	Correct	62 ms	47808 KB	Output is correct
34	Correct	160 ms	47808 KB	Output is correct
35	Correct	1059 ms	47808 KB	Output is correct
36	Correct	1886 ms	47808 KB	Output is correct
37	Correct	1059 ms	47808 KB	Output is correct
38	Correct	1701 ms	47808 KB	Output is correct
39	Correct	959 ms	47808 KB	Output is correct
40	Correct	1137 ms	47808 KB	Output is correct
41	Correct	1110 ms	47808 KB	Output is correct
42	Correct	1118 ms	47808 KB	Output is correct
43	Correct	1097 ms	47808 KB	Output is correct
44	Correct	73 ms	47808 KB	Output is correct
45	Correct	127 ms	47808 KB	Output is correct
46	Correct	173 ms	47808 KB	Output is correct
47	Correct	218 ms	47808 KB	Output is correct
48	Correct	354 ms	47808 KB	Output is correct
49	Correct	1459 ms	48060 KB	Output is correct
50	Correct	1630 ms	48060 KB	Output is correct
51	Correct	1414 ms	48060 KB	Output is correct
52	Correct	2394 ms	48064 KB	Output is correct
53	Correct	1401 ms	48064 KB	Output is correct
54	Correct	1448 ms	48064 KB	Output is correct
55	Correct	1405 ms	48064 KB	Output is correct
56	Correct	149 ms	48064 KB	Output is correct
57	Correct	306 ms	48064 KB	Output is correct
58	Correct	505 ms	48064 KB	Output is correct
59	Correct	1864 ms	48064 KB	Output is correct
60	Correct	2924 ms	48064 KB	Output is correct
61	Correct	1810 ms	48064 KB	Output is correct
62	Correct	1668 ms	48064 KB	Output is correct
63	Correct	2758 ms	48064 KB	Output is correct
64	Correct	1942 ms	48064 KB	Output is correct
65	Correct	1686 ms	48164 KB	Output is correct
66	Correct	1992 ms	48164 KB	Output is correct
67	Correct	1804 ms	48164 KB	Output is correct
68	Correct	1582 ms	48188 KB	Output is correct
69	Correct	2373 ms	48188 KB	Output is correct

답안 #78801

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 6.0 / 6.0

Subtask #3 20.0 / 20.0

Subtask #4 6.0 / 6.0

Subtask #5 33.0 / 33.0

Subtask #6 30.0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
6.0 / 6.0

Subtask #3
20.0 / 20.0

Subtask #4
6.0 / 6.0

Subtask #5
33.0 / 33.0

Subtask #6
30.0 / 30.0