oj.uz

답안 #116234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116234 2019-06-11T11:46:27 Z zubec 자리 배치 (IOI18_seats) C++14
100 / 100
 3128 ms 103416 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> r;

const int SZ = 1000100;

pair<int, int> t[SZ*4];

int ob[SZ*4];

vector <vector<int> > arr;

void build(int v, int l, int r){
    if (l == r){
        t[v].second = 1;
        return;
    }
    int mid = (l+r)>>1;
    build(v+v, l, mid);
    build(v+v+1, mid+1, r);
    t[v].second = t[v+v].second + t[v+v+1].second;
}

inline void push(int v){
    if (ob[v] == 0)
        return;
    t[v+v].first += ob[v];
    t[v+v+1].first += ob[v];
    ob[v+v] += ob[v];
    ob[v+v+1] += ob[v];
    ob[v] = 0;
}

inline void update(int v, int l, int r, int tl, int tr, int x){
    if (l > r || tl > r || l > tr || tl > tr)
        return;
    if (tl <= l && r <= tr){
        t[v].first += x;
        ob[v] += x;
        return;
    }
    int mid = (l+r)>>1;
    push(v);
    update(v+v, l, mid, tl, tr, x);
    update(v+v+1, mid+1, r, tl, tr, x);
    if (t[v+v].first < t[v+v+1].first){
        t[v] = t[v+v];
    } else
    if (t[v+v].first > t[v+v+1].first){
        t[v] = t[v+v+1];
    } else {
        t[v] = {t[v+v].first, t[v+v].second + t[v+v+1].second};
    }
}

int inf;

vector <int> R, C;

inline void upd(int x, int y, int add){
    update(1, 1, inf, arr[x][y] + 1, min({arr[x+1][y], arr[x][y+1], arr[x+1][y+1]}), add);
    update(1, 1, inf, arr[x+1][y] + 1, min({arr[x][y], arr[x][y+1], arr[x+1][y+1]}), add);
    update(1, 1, inf, arr[x][y+1] + 1, min({arr[x][y], arr[x+1][y], arr[x+1][y+1]}), add);
    update(1, 1, inf, arr[x+1][y+1] + 1, min({arr[x][y], arr[x+1][y], arr[x][y+1]}), add);
    update(1, 1, inf, max({arr[x+1][y], arr[x][y+1], arr[x+1][y+1]}) + 1, arr[x][y], add);
    update(1, 1, inf, max({arr[x][y], arr[x][y+1], arr[x+1][y+1]}) + 1, arr[x+1][y], add);
    update(1, 1, inf, max({arr[x][y], arr[x+1][y], arr[x+1][y+1]}) + 1, arr[x][y+1], add);
    update(1, 1, inf, max({arr[x][y], arr[x+1][y], arr[x][y+1]}) + 1, arr[x+1][y+1], add);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    ::R = R;
    ::C = C;
    inf = H*W;
    arr.resize(H+2, vector<int>(W+2, inf));
    for (int i = 0; i < H*W; i++){
        arr[R[i]+1][C[i]+1] = i;
    }
    build(1, 1, inf);

    for (int i = 0; i + 1 < arr.size(); i++){
        for (int j = 0; j + 1 < arr[i].size(); j++){
            upd(i, j, 1);
        }
    }

}


int swap_seats(int a, int b) {
    int x1 = R[a]+1, y1 = C[a]+1, x2 = R[b]+1, y2 = C[b]+1;
    swap(R[a], R[b]);
    swap(C[a], C[b]);
    vector <pair<int, int> > vec;
    vec.push_back({x1-1, y1-1});
    vec.push_back({x1-1, y1});
    vec.push_back({x1, y1-1});
    vec.push_back({x1, y1});
    vec.push_back({x2-1, y2-1});
    vec.push_back({x2-1, y2});
    vec.push_back({x2, y2-1});
    vec.push_back({x2, y2});
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for (int i = 0; i < vec.size(); i++){
        int x = vec[i].first, y = vec[i].second;
        upd(x, y, -1);
    }
    swap(arr[x1][y1], arr[x2][y2]);
    for (int i = 0; i < vec.size(); i++){
        int x = vec[i].first, y = vec[i].second;
        upd(x, y, 1);
    }

    return t[1].second;
}

/**

0 3 4
1 2 5

2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5

*/

Compilation message

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:83:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i + 1 < arr.size(); i++){
                     ~~~~~~^~~~~~~~~~~~
seats.cpp:84:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j + 1 < arr[i].size(); j++){
                         ~~~~~~^~~~~~~~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:107:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~
seats.cpp:112:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 512 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 30 ms 484 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 16 ms 512 KB Output is correct
6 Correct 26 ms 504 KB Output is correct
7 Correct 28 ms 504 KB Output is correct
8 Correct 25 ms 384 KB Output is correct
9 Correct 25 ms 384 KB Output is correct
10 Correct 27 ms 472 KB Output is correct
11 Correct 27 ms 512 KB Output is correct
12 Correct 17 ms 512 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 512 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 30 ms 484 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 16 ms 512 KB Output is correct
6 Correct 26 ms 504 KB Output is correct
7 Correct 28 ms 504 KB Output is correct
8 Correct 25 ms 384 KB Output is correct
9 Correct 25 ms 384 KB Output is correct
10 Correct 27 ms 472 KB Output is correct
11 Correct 27 ms 512 KB Output is correct
12 Correct 17 ms 512 KB Output is correct
13 Correct 86 ms 1152 KB Output is correct
14 Correct 92 ms 1152 KB Output is correct
15 Correct 41 ms 1272 KB Output is correct
16 Correct 31 ms 1664 KB Output is correct
17 Correct 58 ms 1152 KB Output is correct
18 Correct 49 ms 1152 KB Output is correct
19 Correct 45 ms 1272 KB Output is correct
20 Correct 41 ms 1408 KB Output is correct
21 Correct 31 ms 1280 KB Output is correct
22 Correct 32 ms 1664 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1898 ms 52604 KB Output is correct
2 Correct 967 ms 52824 KB Output is correct
3 Correct 931 ms 52732 KB Output is correct
4 Correct 739 ms 52732 KB Output is correct
5 Correct 826 ms 52728 KB Output is correct
6 Correct 740 ms 52696 KB Output is correct
7 Correct 830 ms 52640 KB Output is correct
8 Correct 868 ms 52856 KB Output is correct
9 Correct 867 ms 52808 KB Output is correct
10 Correct 866 ms 52828 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 1160 KB Output is correct
2 Correct 147 ms 6136 KB Output is correct
3 Correct 784 ms 52728 KB Output is correct
4 Correct 2049 ms 52636 KB Output is correct
5 Correct 840 ms 60592 KB Output is correct
6 Correct 1910 ms 103416 KB Output is correct
7 Correct 766 ms 55264 KB Output is correct
8 Correct 1065 ms 52856 KB Output is correct
9 Correct 842 ms 53048 KB Output is correct
10 Correct 885 ms 57284 KB Output is correct
11 Correct 799 ms 75100 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 1512 KB Output is correct
2 Correct 103 ms 1452 KB Output is correct
3 Correct 153 ms 1660 KB Output is correct
4 Correct 243 ms 1604 KB Output is correct
5 Correct 302 ms 2308 KB Output is correct
6 Correct 1144 ms 60612 KB Output is correct
7 Correct 1389 ms 60720 KB Output is correct
8 Correct 1119 ms 60648 KB Output is correct
9 Correct 2531 ms 60772 KB Output is correct
10 Correct 1043 ms 60636 KB Output is correct
11 Correct 1090 ms 60892 KB Output is correct
12 Correct 999 ms 61008 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 512 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 30 ms 484 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 16 ms 512 KB Output is correct
6 Correct 26 ms 504 KB Output is correct
7 Correct 28 ms 504 KB Output is correct
8 Correct 25 ms 384 KB Output is correct
9 Correct 25 ms 384 KB Output is correct
10 Correct 27 ms 472 KB Output is correct
11 Correct 27 ms 512 KB Output is correct
12 Correct 17 ms 512 KB Output is correct
13 Correct 86 ms 1152 KB Output is correct
14 Correct 92 ms 1152 KB Output is correct
15 Correct 41 ms 1272 KB Output is correct
16 Correct 31 ms 1664 KB Output is correct
17 Correct 58 ms 1152 KB Output is correct
18 Correct 49 ms 1152 KB Output is correct
19 Correct 45 ms 1272 KB Output is correct
20 Correct 41 ms 1408 KB Output is correct
21 Correct 31 ms 1280 KB Output is correct
22 Correct 32 ms 1664 KB Output is correct
23 Correct 1898 ms 52604 KB Output is correct
24 Correct 967 ms 52824 KB Output is correct
25 Correct 931 ms 52732 KB Output is correct
26 Correct 739 ms 52732 KB Output is correct
27 Correct 826 ms 52728 KB Output is correct
28 Correct 740 ms 52696 KB Output is correct
29 Correct 830 ms 52640 KB Output is correct
30 Correct 868 ms 52856 KB Output is correct
31 Correct 867 ms 52808 KB Output is correct
32 Correct 866 ms 52828 KB Output is correct
33 Correct 60 ms 1160 KB Output is correct
34 Correct 147 ms 6136 KB Output is correct
35 Correct 784 ms 52728 KB Output is correct
36 Correct 2049 ms 52636 KB Output is correct
37 Correct 840 ms 60592 KB Output is correct
38 Correct 1910 ms 103416 KB Output is correct
39 Correct 766 ms 55264 KB Output is correct
40 Correct 1065 ms 52856 KB Output is correct
41 Correct 842 ms 53048 KB Output is correct
42 Correct 885 ms 57284 KB Output is correct
43 Correct 799 ms 75100 KB Output is correct
44 Correct 54 ms 1512 KB Output is correct
45 Correct 103 ms 1452 KB Output is correct
46 Correct 153 ms 1660 KB Output is correct
47 Correct 243 ms 1604 KB Output is correct
48 Correct 302 ms 2308 KB Output is correct
49 Correct 1144 ms 60612 KB Output is correct
50 Correct 1389 ms 60720 KB Output is correct
51 Correct 1119 ms 60648 KB Output is correct
52 Correct 2531 ms 60772 KB Output is correct
53 Correct 1043 ms 60636 KB Output is correct
54 Correct 1090 ms 60892 KB Output is correct
55 Correct 999 ms 61008 KB Output is correct
56 Correct 132 ms 1596 KB Output is correct
57 Correct 287 ms 1524 KB Output is correct
58 Correct 820 ms 2128 KB Output is correct
59 Correct 1594 ms 53112 KB Output is correct
60 Correct 3022 ms 53088 KB Output is correct
61 Correct 1449 ms 53112 KB Output is correct
62 Correct 1164 ms 57044 KB Output is correct
63 Correct 3128 ms 55672 KB Output is correct
64 Correct 1784 ms 54000 KB Output is correct
65 Correct 1531 ms 53348 KB Output is correct
66 Correct 1621 ms 53428 KB Output is correct
67 Correct 1688 ms 57720 KB Output is correct
68 Correct 1222 ms 67136 KB Output is correct
69 Correct 2728 ms 76532 KB Output is correct