답안 #75159 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75159	2018-09-08T14:18:11 Z	imeimi2000	자리 배치 (IOI18_seats)	C++17	100 / 100	2076 ms	136124 KB

seats

#include "seats.h"
#include <algorithm>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int h, w, n;

vector<int> R, C;
vector<vector<int>> idx;

struct segtree {
    struct node {
        llong mn, ct, lz;
        node operator+(const node &p) const {
            node ret;
            ret.mn = min(mn, p.mn);
            ret.ct = 0;
            if (ret.mn == mn) ret.ct += ct;
            if (ret.mn == p.mn) ret.ct += p.ct;
            ret.lz = 0;
            return ret;
        }
    } seg[1 << 21];
    void init(int i, int s, int e, const vector<llong> &v) {
        if (s == e) {
            seg[i].mn = v[s];
            seg[i].ct = 1;
            seg[i].lz = 0;
            return;
        }
        int m = (s + e) / 2;
        init(i << 1, s, m, v);
        init(i << 1 | 1, m + 1, e, v);
        seg[i] = seg[i << 1] + seg[i << 1 | 1];
    }
    void spread(int i) {
        seg[i << 1].mn += seg[i].lz;
        seg[i << 1].lz += seg[i].lz;
        seg[i << 1 | 1].mn += seg[i].lz;
        seg[i << 1 | 1].lz += seg[i].lz;
        seg[i].lz = 0;
    }
    void update(int i, int s, int e, int x, int y, llong v) {
        if (e < x || y < s) return;
        if (x <= s && e <= y) {
            seg[i].mn += v;
            seg[i].lz += v;
            return;
        }
        spread(i);
        int m = (s + e) / 2;
        update(i << 1, s, m, x, y, v);
        update(i << 1 | 1, m + 1, e, x, y, v);
        seg[i] = seg[i << 1] + seg[i << 1 | 1];
    }
    int get() const {
        return seg[1].ct;
    }
} seg;

int getIdx(int x, int y) {
    if (x < 0 || h <= x || y < 0 || w <= y) return n;
    return idx[x][y];
}

void update(int x, int y, int v) {
    int A[4] = { getIdx(x - 1, y - 1), getIdx(x - 1, y)
                , getIdx(x, y - 1), getIdx(x, y) };
    sort(A, A + 4);
    seg.update(1, 0, n - 1, A[0], A[1] - 1, v);
    seg.update(1, 0, n - 1, A[2], A[3] - 1, v * (1ll << 30));
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    idx.resize(H, vector<int>(W, 0));
    ::R = R; ::C = C;
    h = H; w = W; n = H * W;
    for (int i = 0; i < n; ++i) {
        idx[R[i]][C[i]] = i;
    }
    vector<llong> sum(n + 1, 0);
    for (int i = 0; i <= h; ++i) {
        for (int j = 0; j <= w; ++j) {
            int A[4] = { getIdx(i - 1, j - 1), getIdx(i - 1, j)
                , getIdx(i, j - 1), getIdx(i, j) };
            sort(A, A + 4);
            sum[A[0]] += 1;
            sum[A[1]] -= 1;
            sum[A[2]] += (1ll << 30);
            sum[A[3]] -= (1ll << 30);
        }
    }
    for (int i = 1; i < n; ++i) sum[i] += sum[i - 1];
    seg.init(1, 0, n - 1, sum);
}

int swap_seats(int a, int b) {
    vector<pii> ps;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            ps.emplace_back(R[a] + i, C[a] + j);
            ps.emplace_back(R[b] + i, C[b] + j);
        }
    }
    sort(ps.begin(), ps.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    for (pii i : ps) update(i.first, i.second, -1);
    swap(idx[R[a]][C[a]], idx[R[b]][C[b]]);
    swap(R[a], R[b]); swap(C[a], C[b]);
    for (pii i : ps) update(i.first, i.second, 1);
    return seg.get();
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	376 KB	Output is correct
2	Correct	25 ms	500 KB	Output is correct
3	Correct	37 ms	592 KB	Output is correct
4	Correct	24 ms	756 KB	Output is correct
5	Correct	29 ms	756 KB	Output is correct
6	Correct	46 ms	756 KB	Output is correct
7	Correct	37 ms	756 KB	Output is correct
8	Correct	43 ms	784 KB	Output is correct
9	Correct	31 ms	784 KB	Output is correct
10	Correct	36 ms	784 KB	Output is correct
11	Correct	30 ms	784 KB	Output is correct
12	Correct	23 ms	784 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	376 KB	Output is correct
2	Correct	25 ms	500 KB	Output is correct
3	Correct	37 ms	592 KB	Output is correct
4	Correct	24 ms	756 KB	Output is correct
5	Correct	29 ms	756 KB	Output is correct
6	Correct	46 ms	756 KB	Output is correct
7	Correct	37 ms	756 KB	Output is correct
8	Correct	43 ms	784 KB	Output is correct
9	Correct	31 ms	784 KB	Output is correct
10	Correct	36 ms	784 KB	Output is correct
11	Correct	30 ms	784 KB	Output is correct
12	Correct	23 ms	784 KB	Output is correct
13	Correct	81 ms	1952 KB	Output is correct
14	Correct	86 ms	1952 KB	Output is correct
15	Correct	47 ms	1952 KB	Output is correct
16	Correct	39 ms	2336 KB	Output is correct
17	Correct	63 ms	2336 KB	Output is correct
18	Correct	62 ms	2336 KB	Output is correct
19	Correct	66 ms	2336 KB	Output is correct
20	Correct	55 ms	2336 KB	Output is correct
21	Correct	41 ms	2336 KB	Output is correct
22	Correct	42 ms	2348 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	651 ms	85164 KB	Output is correct
2	Correct	528 ms	85344 KB	Output is correct
3	Correct	523 ms	85344 KB	Output is correct
4	Correct	515 ms	85344 KB	Output is correct
5	Correct	521 ms	85344 KB	Output is correct
6	Correct	561 ms	85344 KB	Output is correct
7	Correct	518 ms	85344 KB	Output is correct
8	Correct	529 ms	85436 KB	Output is correct
9	Correct	531 ms	85436 KB	Output is correct
10	Correct	531 ms	85436 KB	Output is correct

Subtask #4
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	94 ms	85436 KB	Output is correct
2	Correct	126 ms	85436 KB	Output is correct
3	Correct	526 ms	85436 KB	Output is correct
4	Correct	660 ms	85436 KB	Output is correct
5	Correct	508 ms	85436 KB	Output is correct
6	Correct	930 ms	136124 KB	Output is correct
7	Correct	502 ms	136124 KB	Output is correct
8	Correct	656 ms	136124 KB	Output is correct
9	Correct	537 ms	136124 KB	Output is correct
10	Correct	526 ms	136124 KB	Output is correct
11	Correct	726 ms	136124 KB	Output is correct

Subtask #5
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	136124 KB	Output is correct
2	Correct	127 ms	136124 KB	Output is correct
3	Correct	200 ms	136124 KB	Output is correct
4	Correct	282 ms	136124 KB	Output is correct
5	Correct	441 ms	136124 KB	Output is correct
6	Correct	1041 ms	136124 KB	Output is correct
7	Correct	1128 ms	136124 KB	Output is correct
8	Correct	1035 ms	136124 KB	Output is correct
9	Correct	1412 ms	136124 KB	Output is correct
10	Correct	942 ms	136124 KB	Output is correct
11	Correct	967 ms	136124 KB	Output is correct
12	Correct	967 ms	136124 KB	Output is correct

Subtask #6
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	376 KB	Output is correct
2	Correct	25 ms	500 KB	Output is correct
3	Correct	37 ms	592 KB	Output is correct
4	Correct	24 ms	756 KB	Output is correct
5	Correct	29 ms	756 KB	Output is correct
6	Correct	46 ms	756 KB	Output is correct
7	Correct	37 ms	756 KB	Output is correct
8	Correct	43 ms	784 KB	Output is correct
9	Correct	31 ms	784 KB	Output is correct
10	Correct	36 ms	784 KB	Output is correct
11	Correct	30 ms	784 KB	Output is correct
12	Correct	23 ms	784 KB	Output is correct
13	Correct	81 ms	1952 KB	Output is correct
14	Correct	86 ms	1952 KB	Output is correct
15	Correct	47 ms	1952 KB	Output is correct
16	Correct	39 ms	2336 KB	Output is correct
17	Correct	63 ms	2336 KB	Output is correct
18	Correct	62 ms	2336 KB	Output is correct
19	Correct	66 ms	2336 KB	Output is correct
20	Correct	55 ms	2336 KB	Output is correct
21	Correct	41 ms	2336 KB	Output is correct
22	Correct	42 ms	2348 KB	Output is correct
23	Correct	651 ms	85164 KB	Output is correct
24	Correct	528 ms	85344 KB	Output is correct
25	Correct	523 ms	85344 KB	Output is correct
26	Correct	515 ms	85344 KB	Output is correct
27	Correct	521 ms	85344 KB	Output is correct
28	Correct	561 ms	85344 KB	Output is correct
29	Correct	518 ms	85344 KB	Output is correct
30	Correct	529 ms	85436 KB	Output is correct
31	Correct	531 ms	85436 KB	Output is correct
32	Correct	531 ms	85436 KB	Output is correct
33	Correct	94 ms	85436 KB	Output is correct
34	Correct	126 ms	85436 KB	Output is correct
35	Correct	526 ms	85436 KB	Output is correct
36	Correct	660 ms	85436 KB	Output is correct
37	Correct	508 ms	85436 KB	Output is correct
38	Correct	930 ms	136124 KB	Output is correct
39	Correct	502 ms	136124 KB	Output is correct
40	Correct	656 ms	136124 KB	Output is correct
41	Correct	537 ms	136124 KB	Output is correct
42	Correct	526 ms	136124 KB	Output is correct
43	Correct	726 ms	136124 KB	Output is correct
44	Correct	73 ms	136124 KB	Output is correct
45	Correct	127 ms	136124 KB	Output is correct
46	Correct	200 ms	136124 KB	Output is correct
47	Correct	282 ms	136124 KB	Output is correct
48	Correct	441 ms	136124 KB	Output is correct
49	Correct	1041 ms	136124 KB	Output is correct
50	Correct	1128 ms	136124 KB	Output is correct
51	Correct	1035 ms	136124 KB	Output is correct
52	Correct	1412 ms	136124 KB	Output is correct
53	Correct	942 ms	136124 KB	Output is correct
54	Correct	967 ms	136124 KB	Output is correct
55	Correct	967 ms	136124 KB	Output is correct
56	Correct	145 ms	136124 KB	Output is correct
57	Correct	344 ms	136124 KB	Output is correct
58	Correct	621 ms	136124 KB	Output is correct
59	Correct	1539 ms	136124 KB	Output is correct
60	Correct	2076 ms	136124 KB	Output is correct
61	Correct	1372 ms	136124 KB	Output is correct
62	Correct	1132 ms	136124 KB	Output is correct
63	Correct	1841 ms	136124 KB	Output is correct
64	Correct	1525 ms	136124 KB	Output is correct
65	Correct	1398 ms	136124 KB	Output is correct
66	Correct	1591 ms	136124 KB	Output is correct
67	Correct	1469 ms	136124 KB	Output is correct
68	Correct	1218 ms	136124 KB	Output is correct
69	Correct	1907 ms	136124 KB	Output is correct

답안 #75159

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