oj.uz

답안 #647036

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647036 2022-10-01T13:00:59 Z Joshc 자리 배치 (IOI18_seats) C++17
100 / 100
 3071 ms 141748 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

vector<vector<int>> g;
vector<int> r, c;
int h, w;


struct node {
    int min = 0, cnt = 1, lazy = 0;
};

vector<node> seg(4000100);

void push(int v) {
    seg[v<<1].min += seg[v].lazy;
    seg[v<<1|1].min += seg[v].lazy;
    seg[v<<1].lazy += seg[v].lazy;
    seg[v<<1|1].lazy += seg[v].lazy;
    seg[v].lazy = 0;
}

void update(int v, int tl, int tr, int l, int r, ll delta) {
    if (l > r) return;
    if (l == tl && r == tr) {
        seg[v].min += delta;
        seg[v].lazy += delta;
    } else {
        int tm = (tl+tr) >> 1;
        push(v);
        update(v<<1, tl, tm, l, min(r, tm), delta);
        update(v<<1|1, tm+1, tr, max(l, tm+1), r, delta);
        if (seg[v<<1].min == seg[v<<1|1].min) {
            seg[v].min = seg[v<<1].min;
            seg[v].cnt = seg[v<<1].cnt + seg[v<<1|1].cnt;
        } else if (seg[v<<1].min < seg[v<<1|1].min) {
            seg[v].min = seg[v<<1].min;
            seg[v].cnt = seg[v<<1].cnt;
        } else {
            seg[v].min = seg[v<<1|1].min;
            seg[v].cnt = seg[v<<1|1].cnt;
        }
    }
}

void process(int x, int y, int t) {
    // Process the 2*2 square with top-left corner (x, y)
    vector<int> cells;
    for (int i=x; i<x+2; i++) {
        for (int j=y; j<y+2; j++) {
            if (0 <= i && i < h && 0 <= j && j < w) cells.push_back(g[i][j]);
        }
    }
    sort(cells.begin(), cells.end());
    if (cells.size() == 1) update(1, 0, h*w-1, cells[0], h*w-1, t);
    else update(1, 0, h*w-1, cells[0], cells[1]-1, t);
    if (cells.size() == 4) update(1, 0, h*w-1, cells[2], cells[3]-1, 5*t);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    h = H;
    w = W;
    r = R;
    c = C;
    g = vector<vector<int>>(h, vector<int>(w));
    for (int i=0; i<h*w; i++) g[R[i]][C[i]] = i;
    for (int i=-1; i<h; i++) {
        for (int j=-1; j<w; j++) process(i, j, 1);
    }
}

int swap_seats(int a, int b) {
    vector<pair<int, int>> cells;
    for (int i=r[a]-1; i<=r[a]; i++) {
        for (int j=c[a]-1; j<=c[a]; j++) cells.emplace_back(i, j);
    }
    for (int i=r[b]-1; i<=r[b]; i++) {
        for (int j=c[b]-1; j<=c[b]; j++) cells.emplace_back(i, j);
    }
    sort(cells.begin(), cells.end());
    cells.resize(unique(cells.begin(), cells.end())-cells.begin());

    for (auto p : cells) process(p.first, p.second, -1);

    swap(r[a], r[b]);
    swap(c[a], c[b]);
    swap(g[r[a]][c[a]], g[r[b]][c[b]]);
    

    for (auto p : cells) process(p.first, p.second, 1);

    return seg[1].cnt;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 47440 KB Output is correct
2 Correct 47 ms 47416 KB Output is correct
3 Correct 66 ms 47400 KB Output is correct
4 Correct 43 ms 47444 KB Output is correct
5 Correct 39 ms 47408 KB Output is correct
6 Correct 51 ms 47420 KB Output is correct
7 Correct 56 ms 47384 KB Output is correct
8 Correct 55 ms 47436 KB Output is correct
9 Correct 57 ms 47380 KB Output is correct
10 Correct 54 ms 47356 KB Output is correct
11 Correct 61 ms 47396 KB Output is correct
12 Correct 44 ms 47652 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 47440 KB Output is correct
2 Correct 47 ms 47416 KB Output is correct
3 Correct 66 ms 47400 KB Output is correct
4 Correct 43 ms 47444 KB Output is correct
5 Correct 39 ms 47408 KB Output is correct
6 Correct 51 ms 47420 KB Output is correct
7 Correct 56 ms 47384 KB Output is correct
8 Correct 55 ms 47436 KB Output is correct
9 Correct 57 ms 47380 KB Output is correct
10 Correct 54 ms 47356 KB Output is correct
11 Correct 61 ms 47396 KB Output is correct
12 Correct 44 ms 47652 KB Output is correct
13 Correct 99 ms 47756 KB Output is correct
14 Correct 107 ms 47752 KB Output is correct
15 Correct 78 ms 47796 KB Output is correct
16 Correct 66 ms 48388 KB Output is correct
17 Correct 114 ms 47772 KB Output is correct
18 Correct 86 ms 47704 KB Output is correct
19 Correct 80 ms 47788 KB Output is correct
20 Correct 73 ms 47980 KB Output is correct
21 Correct 81 ms 47708 KB Output is correct
22 Correct 65 ms 48212 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1931 ms 90740 KB Output is correct
2 Correct 1099 ms 90740 KB Output is correct
3 Correct 1070 ms 90784 KB Output is correct
4 Correct 912 ms 90788 KB Output is correct
5 Correct 953 ms 90824 KB Output is correct
6 Correct 980 ms 90752 KB Output is correct
7 Correct 984 ms 90752 KB Output is correct
8 Correct 1012 ms 90744 KB Output is correct
9 Correct 1055 ms 90740 KB Output is correct
10 Correct 1008 ms 90672 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 47764 KB Output is correct
2 Correct 191 ms 51036 KB Output is correct
3 Correct 976 ms 90740 KB Output is correct
4 Correct 1871 ms 90732 KB Output is correct
5 Correct 876 ms 94644 KB Output is correct
6 Correct 1949 ms 141748 KB Output is correct
7 Correct 953 ms 91948 KB Output is correct
8 Correct 1066 ms 90740 KB Output is correct
9 Correct 996 ms 91108 KB Output is correct
10 Correct 1012 ms 93932 KB Output is correct
11 Correct 946 ms 114252 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 48968 KB Output is correct
2 Correct 169 ms 48896 KB Output is correct
3 Correct 235 ms 48980 KB Output is correct
4 Correct 282 ms 48980 KB Output is correct
5 Correct 420 ms 49408 KB Output is correct
6 Correct 1393 ms 95564 KB Output is correct
7 Correct 1536 ms 95560 KB Output is correct
8 Correct 1334 ms 95560 KB Output is correct
9 Correct 2369 ms 95528 KB Output is correct
10 Correct 1306 ms 95708 KB Output is correct
11 Correct 1306 ms 95564 KB Output is correct
12 Correct 1251 ms 95564 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 47440 KB Output is correct
2 Correct 47 ms 47416 KB Output is correct
3 Correct 66 ms 47400 KB Output is correct
4 Correct 43 ms 47444 KB Output is correct
5 Correct 39 ms 47408 KB Output is correct
6 Correct 51 ms 47420 KB Output is correct
7 Correct 56 ms 47384 KB Output is correct
8 Correct 55 ms 47436 KB Output is correct
9 Correct 57 ms 47380 KB Output is correct
10 Correct 54 ms 47356 KB Output is correct
11 Correct 61 ms 47396 KB Output is correct
12 Correct 44 ms 47652 KB Output is correct
13 Correct 99 ms 47756 KB Output is correct
14 Correct 107 ms 47752 KB Output is correct
15 Correct 78 ms 47796 KB Output is correct
16 Correct 66 ms 48388 KB Output is correct
17 Correct 114 ms 47772 KB Output is correct
18 Correct 86 ms 47704 KB Output is correct
19 Correct 80 ms 47788 KB Output is correct
20 Correct 73 ms 47980 KB Output is correct
21 Correct 81 ms 47708 KB Output is correct
22 Correct 65 ms 48212 KB Output is correct
23 Correct 1931 ms 90740 KB Output is correct
24 Correct 1099 ms 90740 KB Output is correct
25 Correct 1070 ms 90784 KB Output is correct
26 Correct 912 ms 90788 KB Output is correct
27 Correct 953 ms 90824 KB Output is correct
28 Correct 980 ms 90752 KB Output is correct
29 Correct 984 ms 90752 KB Output is correct
30 Correct 1012 ms 90744 KB Output is correct
31 Correct 1055 ms 90740 KB Output is correct
32 Correct 1008 ms 90672 KB Output is correct
33 Correct 101 ms 47764 KB Output is correct
34 Correct 191 ms 51036 KB Output is correct
35 Correct 976 ms 90740 KB Output is correct
36 Correct 1871 ms 90732 KB Output is correct
37 Correct 876 ms 94644 KB Output is correct
38 Correct 1949 ms 141748 KB Output is correct
39 Correct 953 ms 91948 KB Output is correct
40 Correct 1066 ms 90740 KB Output is correct
41 Correct 996 ms 91108 KB Output is correct
42 Correct 1012 ms 93932 KB Output is correct
43 Correct 946 ms 114252 KB Output is correct
44 Correct 109 ms 48968 KB Output is correct
45 Correct 169 ms 48896 KB Output is correct
46 Correct 235 ms 48980 KB Output is correct
47 Correct 282 ms 48980 KB Output is correct
48 Correct 420 ms 49408 KB Output is correct
49 Correct 1393 ms 95564 KB Output is correct
50 Correct 1536 ms 95560 KB Output is correct
51 Correct 1334 ms 95560 KB Output is correct
52 Correct 2369 ms 95528 KB Output is correct
53 Correct 1306 ms 95708 KB Output is correct
54 Correct 1306 ms 95564 KB Output is correct
55 Correct 1251 ms 95564 KB Output is correct
56 Correct 184 ms 48968 KB Output is correct
57 Correct 379 ms 48960 KB Output is correct
58 Correct 584 ms 49412 KB Output is correct
59 Correct 1756 ms 91804 KB Output is correct
60 Correct 2899 ms 91816 KB Output is correct
61 Correct 1661 ms 91820 KB Output is correct
62 Correct 1397 ms 93604 KB Output is correct
63 Correct 2828 ms 92904 KB Output is correct
64 Correct 1878 ms 92076 KB Output is correct
65 Correct 1690 ms 91700 KB Output is correct
66 Correct 1920 ms 92052 KB Output is correct
67 Correct 2082 ms 94768 KB Output is correct
68 Correct 1697 ms 106092 KB Output is correct
69 Correct 3071 ms 115148 KB Output is correct