oj.uz

답안 #116233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116233 2019-06-11T11:38:54 Z zubec 자리 배치 (IOI18_seats) C++14
100 / 100
 3252 ms 104312 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;
}

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;
}

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;

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]);
    map<pair<int, int>, int> mp1;
    mp1[{x1-1, y1-1}] = 1;
    mp1[{x1-1, y1}] = 1;
    mp1[{x1, y1-1}] = 1;
    mp1[{x1, y1}] = 1;
    mp1[{x2-1, y2-1}] = 1;
    mp1[{x2-1, y2}] = 1;
    mp1[{x2, y2-1}] = 1;
    mp1[{x2, y2}] = 1;
    for (auto it = mp1.begin(); it != mp1.end(); it++){
        int x = it->first.first, y = it->first.second;
        upd(x, y, -1);
    }
    swap(arr[x1][y1], arr[x2][y2]);
    for (auto it = mp1.begin(); it != mp1.end(); it++){
        int x = it->first.first, y = it->first.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++){
                         ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 512 KB Output is correct
2 Correct 23 ms 384 KB Output is correct
3 Correct 33 ms 384 KB Output is correct
4 Correct 23 ms 512 KB Output is correct
5 Correct 18 ms 512 KB Output is correct
6 Correct 29 ms 384 KB Output is correct
7 Correct 32 ms 504 KB Output is correct
8 Correct 29 ms 384 KB Output is correct
9 Correct 29 ms 504 KB Output is correct
10 Correct 32 ms 504 KB Output is correct
11 Correct 28 ms 504 KB Output is correct
12 Correct 19 ms 512 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 512 KB Output is correct
2 Correct 23 ms 384 KB Output is correct
3 Correct 33 ms 384 KB Output is correct
4 Correct 23 ms 512 KB Output is correct
5 Correct 18 ms 512 KB Output is correct
6 Correct 29 ms 384 KB Output is correct
7 Correct 32 ms 504 KB Output is correct
8 Correct 29 ms 384 KB Output is correct
9 Correct 29 ms 504 KB Output is correct
10 Correct 32 ms 504 KB Output is correct
11 Correct 28 ms 504 KB Output is correct
12 Correct 19 ms 512 KB Output is correct
13 Correct 126 ms 1272 KB Output is correct
14 Correct 80 ms 1244 KB Output is correct
15 Correct 47 ms 1272 KB Output is correct
16 Correct 35 ms 1784 KB Output is correct
17 Correct 58 ms 1276 KB Output is correct
18 Correct 57 ms 1272 KB Output is correct
19 Correct 52 ms 1272 KB Output is correct
20 Correct 58 ms 1444 KB Output is correct
21 Correct 37 ms 1332 KB Output is correct
22 Correct 40 ms 1664 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2163 ms 53112 KB Output is correct
2 Correct 1194 ms 53084 KB Output is correct
3 Correct 987 ms 53152 KB Output is correct
4 Correct 818 ms 53368 KB Output is correct
5 Correct 871 ms 53240 KB Output is correct
6 Correct 803 ms 53240 KB Output is correct
7 Correct 896 ms 53240 KB Output is correct
8 Correct 962 ms 53212 KB Output is correct
9 Correct 990 ms 53240 KB Output is correct
10 Correct 922 ms 53244 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 1144 KB Output is correct
2 Correct 163 ms 6616 KB Output is correct
3 Correct 855 ms 53444 KB Output is correct
4 Correct 2090 ms 53496 KB Output is correct
5 Correct 780 ms 61232 KB Output is correct
6 Correct 2016 ms 104312 KB Output is correct
7 Correct 901 ms 56032 KB Output is correct
8 Correct 1160 ms 53624 KB Output is correct
9 Correct 958 ms 53880 KB Output is correct
10 Correct 926 ms 58104 KB Output is correct
11 Correct 920 ms 75996 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 1752 KB Output is correct
2 Correct 133 ms 1800 KB Output is correct
3 Correct 183 ms 1928 KB Output is correct
4 Correct 229 ms 1768 KB Output is correct
5 Correct 351 ms 2564 KB Output is correct
6 Correct 1240 ms 60772 KB Output is correct
7 Correct 1491 ms 60720 KB Output is correct
8 Correct 1183 ms 60720 KB Output is correct
9 Correct 2642 ms 60848 KB Output is correct
10 Correct 1168 ms 60852 KB Output is correct
11 Correct 1185 ms 62256 KB Output is correct
12 Correct 1109 ms 62264 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 512 KB Output is correct
2 Correct 23 ms 384 KB Output is correct
3 Correct 33 ms 384 KB Output is correct
4 Correct 23 ms 512 KB Output is correct
5 Correct 18 ms 512 KB Output is correct
6 Correct 29 ms 384 KB Output is correct
7 Correct 32 ms 504 KB Output is correct
8 Correct 29 ms 384 KB Output is correct
9 Correct 29 ms 504 KB Output is correct
10 Correct 32 ms 504 KB Output is correct
11 Correct 28 ms 504 KB Output is correct
12 Correct 19 ms 512 KB Output is correct
13 Correct 126 ms 1272 KB Output is correct
14 Correct 80 ms 1244 KB Output is correct
15 Correct 47 ms 1272 KB Output is correct
16 Correct 35 ms 1784 KB Output is correct
17 Correct 58 ms 1276 KB Output is correct
18 Correct 57 ms 1272 KB Output is correct
19 Correct 52 ms 1272 KB Output is correct
20 Correct 58 ms 1444 KB Output is correct
21 Correct 37 ms 1332 KB Output is correct
22 Correct 40 ms 1664 KB Output is correct
23 Correct 2163 ms 53112 KB Output is correct
24 Correct 1194 ms 53084 KB Output is correct
25 Correct 987 ms 53152 KB Output is correct
26 Correct 818 ms 53368 KB Output is correct
27 Correct 871 ms 53240 KB Output is correct
28 Correct 803 ms 53240 KB Output is correct
29 Correct 896 ms 53240 KB Output is correct
30 Correct 962 ms 53212 KB Output is correct
31 Correct 990 ms 53240 KB Output is correct
32 Correct 922 ms 53244 KB Output is correct
33 Correct 66 ms 1144 KB Output is correct
34 Correct 163 ms 6616 KB Output is correct
35 Correct 855 ms 53444 KB Output is correct
36 Correct 2090 ms 53496 KB Output is correct
37 Correct 780 ms 61232 KB Output is correct
38 Correct 2016 ms 104312 KB Output is correct
39 Correct 901 ms 56032 KB Output is correct
40 Correct 1160 ms 53624 KB Output is correct
41 Correct 958 ms 53880 KB Output is correct
42 Correct 926 ms 58104 KB Output is correct
43 Correct 920 ms 75996 KB Output is correct
44 Correct 76 ms 1752 KB Output is correct
45 Correct 133 ms 1800 KB Output is correct
46 Correct 183 ms 1928 KB Output is correct
47 Correct 229 ms 1768 KB Output is correct
48 Correct 351 ms 2564 KB Output is correct
49 Correct 1240 ms 60772 KB Output is correct
50 Correct 1491 ms 60720 KB Output is correct
51 Correct 1183 ms 60720 KB Output is correct
52 Correct 2642 ms 60848 KB Output is correct
53 Correct 1168 ms 60852 KB Output is correct
54 Correct 1185 ms 62256 KB Output is correct
55 Correct 1109 ms 62264 KB Output is correct
56 Correct 149 ms 2020 KB Output is correct
57 Correct 326 ms 2048 KB Output is correct
58 Correct 485 ms 2812 KB Output is correct
59 Correct 1743 ms 54516 KB Output is correct
60 Correct 3252 ms 54556 KB Output is correct
61 Correct 1588 ms 54648 KB Output is correct
62 Correct 1277 ms 58360 KB Output is correct
63 Correct 3239 ms 57188 KB Output is correct
64 Correct 1966 ms 55280 KB Output is correct
65 Correct 1752 ms 54520 KB Output is correct
66 Correct 2138 ms 55036 KB Output is correct
67 Correct 1873 ms 59256 KB Output is correct
68 Correct 1404 ms 67320 KB Output is correct
69 Correct 2937 ms 77944 KB Output is correct