oj.uz

답안 #403115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403115 2021-05-12T19:03:01 Z jhnah917 자리 배치 (IOI18_seats) C++14
100 / 100
 2570 ms 102512 KB 
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#ifndef LOCAL
#include "seats.h"
#endif
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using PII = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;

int N, M, K, A[1 << 20];
vector<int> X, Y;
vector<vector<int>> V;
PII T[1 << 21]; int L[1 << 21];

PII Merge(const PII &l, const PII &r){
    return l.x == r.x ? PII(l.x, l.y+r.y) : min(l, r);
}
void Push(int node, int s, int e){
    T[node].x += L[node];
    if(s != e) L[node<<1] += L[node], L[node<<1|1] += L[node];
    L[node] = 0;
}
void Init(int node=1, int s=1, int e=K){
    if(s == e){ T[node] = {A[s], 1}; return; }
    int m = s + e >> 1;
    Init(node<<1, s, m); Init(node<<1|1, m+1, e);
    T[node] = Merge(T[node<<1], T[node<<1|1]);
}
void Update(int l, int r, int v, int node=1, int s=1, int e=K){
    Push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){ L[node] += v; Push(node, s, e); return; }
    int m = s + e >> 1;
    Update(l, r, v, node<<1, s, m);
    Update(l, r, v, node<<1|1, m+1, e);
    T[node] = Merge(T[node<<1], T[node<<1|1]);
}

void give_initial_chart(int H, int W, vector<int> _R, vector<int> _C){
    N = H; M = W; K = N * M;
    swap(X, _R); swap(Y, _C);

    V = vector<vector<int>>(N+2, vector<int>(M+2, K+1));
    for(int i=0; i<K; i++) V[++X[i]][++Y[i]] = i+1;

    for(int i=0; i<=N; i++){
        for(int j=0; j<=M; j++){
            vector<int> tmp = {V[i][j], V[i+1][j], V[i][j+1], V[i+1][j+1]};
            sort(tmp.begin(), tmp.end());
            A[tmp[0]]++; A[tmp[1]]--;
            A[tmp[2]]++; A[tmp[3]]--;
        }
    }
    partial_sum(A, A+(1<<20), A);
    Init();
}

void Change(int x, int y, int v){
    for(int dx=0; dx<2; dx++) for(int dy=0; dy<2; dy++) {
        int i = x - dx, j = y - dy;
        vector<int> tmp = {V[i][j], V[i+1][j], V[i][j+1], V[i+1][j+1]};
        sort(tmp.begin(), tmp.end());
        Update(tmp[0], tmp[1]-1, v);
        Update(tmp[2], tmp[3]-1, v);
    }
}

int swap_seats(int a, int b){
    Change(X[a], Y[a], -1); Change(X[b], Y[b], -1);
    swap(X[a], X[b]); swap(Y[a], Y[b]);
    swap(V[X[a]][Y[a]], V[X[b]][Y[b]]);
    Change(X[a], Y[a], +1); Change(X[b], Y[b], +1);
    return T[1].x == 4 ? T[1].y : 0;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int H, W, Q;
    cin >> H >> W >> Q;
    vector<int> R(H*W), C(H*W);
    for(int i=0; i<H*W; i++) cin >> R[i] >> C[i];
    vector<int> A(Q), B(Q);
    for(int i=0; i<Q; i++) cin >> A[i] >> B[i];
    give_initial_chart(H, W, R, C);
    for(int i=0; i<Q; i++){
        cout << swap_seats(A[i], B[i]) << "\n";
    }
    return 0;
}
#endif

/*
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 Init(int, int, int)':
seats.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int m = s + e >> 1;
      |             ~~^~~
seats.cpp: In function 'void Update(int, int, int, int, int, int)':
seats.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int m = s + e >> 1;
      |             ~~^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 4524 KB Output is correct
2 Correct 32 ms 4532 KB Output is correct
3 Correct 49 ms 4640 KB Output is correct
4 Correct 31 ms 4548 KB Output is correct
5 Correct 27 ms 4520 KB Output is correct
6 Correct 42 ms 4532 KB Output is correct
7 Correct 45 ms 4548 KB Output is correct
8 Correct 46 ms 4540 KB Output is correct
9 Correct 49 ms 4540 KB Output is correct
10 Correct 47 ms 4524 KB Output is correct
11 Correct 42 ms 4552 KB Output is correct
12 Correct 28 ms 4544 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 4524 KB Output is correct
2 Correct 32 ms 4532 KB Output is correct
3 Correct 49 ms 4640 KB Output is correct
4 Correct 31 ms 4548 KB Output is correct
5 Correct 27 ms 4520 KB Output is correct
6 Correct 42 ms 4532 KB Output is correct
7 Correct 45 ms 4548 KB Output is correct
8 Correct 46 ms 4540 KB Output is correct
9 Correct 49 ms 4540 KB Output is correct
10 Correct 47 ms 4524 KB Output is correct
11 Correct 42 ms 4552 KB Output is correct
12 Correct 28 ms 4544 KB Output is correct
13 Correct 101 ms 5260 KB Output is correct
14 Correct 117 ms 5212 KB Output is correct
15 Correct 66 ms 5328 KB Output is correct
16 Correct 58 ms 5852 KB Output is correct
17 Correct 82 ms 5304 KB Output is correct
18 Correct 85 ms 5164 KB Output is correct
19 Correct 78 ms 5248 KB Output is correct
20 Correct 66 ms 5452 KB Output is correct
21 Correct 63 ms 5308 KB Output is correct
22 Correct 55 ms 5740 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 631 ms 51156 KB Output is correct
2 Correct 502 ms 51152 KB Output is correct
3 Correct 504 ms 51260 KB Output is correct
4 Correct 484 ms 51136 KB Output is correct
5 Correct 493 ms 51156 KB Output is correct
6 Correct 502 ms 51136 KB Output is correct
7 Correct 483 ms 51136 KB Output is correct
8 Correct 493 ms 51132 KB Output is correct
9 Correct 485 ms 51124 KB Output is correct
10 Correct 525 ms 51108 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 5280 KB Output is correct
2 Correct 156 ms 10476 KB Output is correct
3 Correct 489 ms 51580 KB Output is correct
4 Correct 639 ms 51644 KB Output is correct
5 Correct 507 ms 59312 KB Output is correct
6 Correct 842 ms 102512 KB Output is correct
7 Correct 547 ms 54216 KB Output is correct
8 Correct 517 ms 51648 KB Output is correct
9 Correct 520 ms 51992 KB Output is correct
10 Correct 574 ms 56248 KB Output is correct
11 Correct 534 ms 75128 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 6072 KB Output is correct
2 Correct 178 ms 6076 KB Output is correct
3 Correct 251 ms 6148 KB Output is correct
4 Correct 395 ms 6156 KB Output is correct
5 Correct 589 ms 6924 KB Output is correct
6 Correct 1328 ms 59420 KB Output is correct
7 Correct 1278 ms 60452 KB Output is correct
8 Correct 1210 ms 60552 KB Output is correct
9 Correct 1486 ms 60532 KB Output is correct
10 Correct 1115 ms 60556 KB Output is correct
11 Correct 1160 ms 57780 KB Output is correct
12 Correct 1104 ms 57936 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 4524 KB Output is correct
2 Correct 32 ms 4532 KB Output is correct
3 Correct 49 ms 4640 KB Output is correct
4 Correct 31 ms 4548 KB Output is correct
5 Correct 27 ms 4520 KB Output is correct
6 Correct 42 ms 4532 KB Output is correct
7 Correct 45 ms 4548 KB Output is correct
8 Correct 46 ms 4540 KB Output is correct
9 Correct 49 ms 4540 KB Output is correct
10 Correct 47 ms 4524 KB Output is correct
11 Correct 42 ms 4552 KB Output is correct
12 Correct 28 ms 4544 KB Output is correct
13 Correct 101 ms 5260 KB Output is correct
14 Correct 117 ms 5212 KB Output is correct
15 Correct 66 ms 5328 KB Output is correct
16 Correct 58 ms 5852 KB Output is correct
17 Correct 82 ms 5304 KB Output is correct
18 Correct 85 ms 5164 KB Output is correct
19 Correct 78 ms 5248 KB Output is correct
20 Correct 66 ms 5452 KB Output is correct
21 Correct 63 ms 5308 KB Output is correct
22 Correct 55 ms 5740 KB Output is correct
23 Correct 631 ms 51156 KB Output is correct
24 Correct 502 ms 51152 KB Output is correct
25 Correct 504 ms 51260 KB Output is correct
26 Correct 484 ms 51136 KB Output is correct
27 Correct 493 ms 51156 KB Output is correct
28 Correct 502 ms 51136 KB Output is correct
29 Correct 483 ms 51136 KB Output is correct
30 Correct 493 ms 51132 KB Output is correct
31 Correct 485 ms 51124 KB Output is correct
32 Correct 525 ms 51108 KB Output is correct
33 Correct 134 ms 5280 KB Output is correct
34 Correct 156 ms 10476 KB Output is correct
35 Correct 489 ms 51580 KB Output is correct
36 Correct 639 ms 51644 KB Output is correct
37 Correct 507 ms 59312 KB Output is correct
38 Correct 842 ms 102512 KB Output is correct
39 Correct 547 ms 54216 KB Output is correct
40 Correct 517 ms 51648 KB Output is correct
41 Correct 520 ms 51992 KB Output is correct
42 Correct 574 ms 56248 KB Output is correct
43 Correct 534 ms 75128 KB Output is correct
44 Correct 124 ms 6072 KB Output is correct
45 Correct 178 ms 6076 KB Output is correct
46 Correct 251 ms 6148 KB Output is correct
47 Correct 395 ms 6156 KB Output is correct
48 Correct 589 ms 6924 KB Output is correct
49 Correct 1328 ms 59420 KB Output is correct
50 Correct 1278 ms 60452 KB Output is correct
51 Correct 1210 ms 60552 KB Output is correct
52 Correct 1486 ms 60532 KB Output is correct
53 Correct 1115 ms 60556 KB Output is correct
54 Correct 1160 ms 57780 KB Output is correct
55 Correct 1104 ms 57936 KB Output is correct
56 Correct 188 ms 6076 KB Output is correct
57 Correct 471 ms 6028 KB Output is correct
58 Correct 800 ms 6720 KB Output is correct
59 Correct 1758 ms 49656 KB Output is correct
60 Correct 2570 ms 49640 KB Output is correct
61 Correct 1556 ms 49712 KB Output is correct
62 Correct 1358 ms 70180 KB Output is correct
63 Correct 2182 ms 68892 KB Output is correct
64 Correct 1754 ms 67232 KB Output is correct
65 Correct 1569 ms 66276 KB Output is correct
66 Correct 1856 ms 66548 KB Output is correct
67 Correct 1825 ms 71056 KB Output is correct
68 Correct 1403 ms 80588 KB Output is correct
69 Correct 2120 ms 89696 KB Output is correct