oj.uz

답안 #75417

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75417 2018-09-09T15:48:16 Z mammamia 자리 배치 (IOI18_seats) C++14
100 / 100
 3135 ms 111776 KB 
#include "seats.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int NMAX = 4000005;

const int dxa[] = {1, 0, -1, 0};
const int dya[] = {0, 1, 0, -1};

const int dxb[] = {0, -1, -1};
const int dyb[] = {-1, -1, 0};

const int dxbdown[] = {0, 1, 1};
const int dybdown[] = {1, 1, 0};

typedef pair<int, int> pii;

pii t[4*NMAX];
int lz[4*NMAX];
pii seats[4000555];
int tsz, H, W;

void updateAtPositionA(pii pos);
void deleteAtPositionA(pii pos);
void updateAtPositionB(pii pos);
void deleteAtPositionB(pii pos);
int secondSmallestNeighbourA(pii pos);
pii getCornerIntervalB(pii pos);
bool inBound(pii pos);
void addInterval(int l, int r);
void subInterval(int l, int r);
void rewriteAtPosition(pii pos, int val);

vector<vector<int>> arr;

int ln(int n){
    return 2*n;
}
int rn(int n){
    return 2*n + 1;
}

pii tcombine(pii a, pii b){
    if(a.first < b.first){
        return a;
    } else if(a.first > b.first) {
        return b;
    } else {
        return {a.first, a.second + b.second};
    }
}

void push(int n){
    if(lz[n]){
        t[n].first += lz[n];
        lz[ln(n)] += lz[n];
        lz[rn(n)] += lz[n];
        lz[n] = 0;
    }
}

void build(int n, int l, int r){
    if(l == r){
        t[n] = {0, 1};
        return;
    }
    int pivot = (l+r)>>1;
    build(ln(n), l, pivot);
    build(rn(n), pivot + 1, r);

    t[n] = tcombine(t[ln(n)], t[rn(n)]);
}

void update(int n, int l, int r, int ql, int qr, int add){
    push(n);
    if(ql <= l && r <= qr){
        lz[n] += add;
        push(n);
        return;
    }
    int pivot = (l+r)>>1;
    if(ql <= pivot)
        update(ln(n), l, pivot, ql, qr, add);
    if(qr > pivot)
        update(rn(n), pivot+1, r, ql, qr, add);

    push(ln(n));
    push(rn(n));
    t[n] = tcombine(t[ln(n)], t[rn(n)]);

}

void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
    W = _W;
    H = _H;
    tsz = H*W; // add the right endpoint
    build(1, 1, tsz);
    arr = vector<vector<int>>(H+1, vector<int>(W+1, 0));

    for(int i=0; i<H*W; ++i){
        arr[R[i] + 1][C[i] + 1] = i + 1;
        seats[i] = {R[i] + 1, C[i] + 1};
    }
    for(int i = 1; i<=H; ++i){
        for(int j = 1; j<=W; ++j)
        {
            updateAtPositionA({i, j});
            updateAtPositionB({i, j});
        }
    }
    //cout<<t[1].first<<" "<<t[1].second<<"\n";

}

int swap_seats(int a, int b) {
    pii pa = seats[a];
    pii pb = seats[b];

    //cout<<"swap "<<a<<" "<<b<<"\n";


    rewriteAtPosition(pa, b + 1);
    rewriteAtPosition(pb, a + 1);

    swap(seats[a], seats[b]);


    return (t[1].first == 1 ? t[1].second : 0);
}

void rewriteAtPosition(pii pos, int val){

    // delete previous connections
    deleteAtPositionA(pos);
    for(int i=0; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            deleteAtPositionA(aux);
        }
    }
    deleteAtPositionB(pos);
    for(int i=2; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            deleteAtPositionB(aux);
        }
    }

    //rewrite
    arr[pos.x][pos.y] = val;

    // add the new connections
    updateAtPositionA(pos);
    for(int i=0; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            updateAtPositionA(aux);
        }
    }
    updateAtPositionB(pos);
    for(int i=2; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            updateAtPositionB(aux);
        }
    }
}


void deleteAtPositionA(pii pos){
    int l = secondSmallestNeighbourA(pos);
    int r = arr[pos.x][pos.y];
    if(r > l){
        subInterval(l, r - 1);
    }
}

void updateAtPositionA(pii pos){
    int l = secondSmallestNeighbourA(pos);
    int r = arr[pos.x][pos.y];
    if(r > l){
        addInterval(l, r - 1);
    }
}

void deleteAtPositionB(pii pos){
    pii p = getCornerIntervalB(pos);
    if(p.y > p.x){
        subInterval(p.x, p.y - 1);
    }
}

void updateAtPositionB(pii pos){
    pii p = getCornerIntervalB(pos);
    if(p.y > p.x){
        addInterval(p.x, p.y - 1);
    }
}

int secondSmallestNeighbourA(pii pos){
    set<int> countSet;
    for(int i=0; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            countSet.insert(arr[aux.x][aux.y]);
        }
    }
    if(countSet.size() > 1){
        return *(++countSet.begin());
    } else {
        return tsz+1;
    }
}

pii getCornerIntervalB(pii pos){
    int l = arr[pos.x][pos.y];
    int r = tsz + 1;
    for(int i=0; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            if(i < 2)
                r = min(r, arr[aux.x][aux.y]);
        }
    }
    //cout<<"corner for "<<pos.x<<" "<<pos.y<<" "<<l<<" "<<r<<"\n";
    return {l, r};
}

bool inBound(pii pos){
    if(pos.x > 0 && pos.x <= H){
        if(pos.y > 0 && pos.y <= W){
            return 1;
        }
    }
    return 0;
}

void addInterval(int l, int r){

    //cout<<"add "<<l<<" "<<r<<"\n";
    update(1, 1, tsz, l, r, +1);
}

void subInterval(int l, int r){
    //cout<<"sub "<<l<<" "<<r<<"\n";
    update(1, 1, tsz, l, r, -1);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 504 KB Output is correct
2 Correct 36 ms 508 KB Output is correct
3 Correct 47 ms 568 KB Output is correct
4 Correct 23 ms 568 KB Output is correct
5 Correct 56 ms 616 KB Output is correct
6 Correct 34 ms 744 KB Output is correct
7 Correct 41 ms 744 KB Output is correct
8 Correct 41 ms 760 KB Output is correct
9 Correct 44 ms 760 KB Output is correct
10 Correct 44 ms 760 KB Output is correct
11 Correct 39 ms 760 KB Output is correct
12 Correct 19 ms 760 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 504 KB Output is correct
2 Correct 36 ms 508 KB Output is correct
3 Correct 47 ms 568 KB Output is correct
4 Correct 23 ms 568 KB Output is correct
5 Correct 56 ms 616 KB Output is correct
6 Correct 34 ms 744 KB Output is correct
7 Correct 41 ms 744 KB Output is correct
8 Correct 41 ms 760 KB Output is correct
9 Correct 44 ms 760 KB Output is correct
10 Correct 44 ms 760 KB Output is correct
11 Correct 39 ms 760 KB Output is correct
12 Correct 19 ms 760 KB Output is correct
13 Correct 83 ms 1364 KB Output is correct
14 Correct 89 ms 1364 KB Output is correct
15 Correct 43 ms 1640 KB Output is correct
16 Correct 38 ms 1912 KB Output is correct
17 Correct 58 ms 1912 KB Output is correct
18 Correct 76 ms 1912 KB Output is correct
19 Correct 65 ms 1912 KB Output is correct
20 Correct 43 ms 1912 KB Output is correct
21 Correct 33 ms 1912 KB Output is correct
22 Correct 36 ms 1952 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1970 ms 60960 KB Output is correct
2 Correct 1226 ms 61160 KB Output is correct
3 Correct 1125 ms 61160 KB Output is correct
4 Correct 1010 ms 61160 KB Output is correct
5 Correct 1117 ms 61160 KB Output is correct
6 Correct 979 ms 61160 KB Output is correct
7 Correct 1103 ms 61160 KB Output is correct
8 Correct 1112 ms 61160 KB Output is correct
9 Correct 950 ms 61160 KB Output is correct
10 Correct 1079 ms 61184 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 61184 KB Output is correct
2 Correct 234 ms 61184 KB Output is correct
3 Correct 868 ms 61184 KB Output is correct
4 Correct 1993 ms 61184 KB Output is correct
5 Correct 534 ms 61184 KB Output is correct
6 Correct 1753 ms 111776 KB Output is correct
7 Correct 1063 ms 111776 KB Output is correct
8 Correct 1149 ms 111776 KB Output is correct
9 Correct 1144 ms 111776 KB Output is correct
10 Correct 1254 ms 111776 KB Output is correct
11 Correct 958 ms 111776 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 111776 KB Output is correct
2 Correct 135 ms 111776 KB Output is correct
3 Correct 173 ms 111776 KB Output is correct
4 Correct 219 ms 111776 KB Output is correct
5 Correct 327 ms 111776 KB Output is correct
6 Correct 1275 ms 111776 KB Output is correct
7 Correct 1255 ms 111776 KB Output is correct
8 Correct 828 ms 111776 KB Output is correct
9 Correct 2060 ms 111776 KB Output is correct
10 Correct 1200 ms 111776 KB Output is correct
11 Correct 1110 ms 111776 KB Output is correct
12 Correct 1133 ms 111776 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 504 KB Output is correct
2 Correct 36 ms 508 KB Output is correct
3 Correct 47 ms 568 KB Output is correct
4 Correct 23 ms 568 KB Output is correct
5 Correct 56 ms 616 KB Output is correct
6 Correct 34 ms 744 KB Output is correct
7 Correct 41 ms 744 KB Output is correct
8 Correct 41 ms 760 KB Output is correct
9 Correct 44 ms 760 KB Output is correct
10 Correct 44 ms 760 KB Output is correct
11 Correct 39 ms 760 KB Output is correct
12 Correct 19 ms 760 KB Output is correct
13 Correct 83 ms 1364 KB Output is correct
14 Correct 89 ms 1364 KB Output is correct
15 Correct 43 ms 1640 KB Output is correct
16 Correct 38 ms 1912 KB Output is correct
17 Correct 58 ms 1912 KB Output is correct
18 Correct 76 ms 1912 KB Output is correct
19 Correct 65 ms 1912 KB Output is correct
20 Correct 43 ms 1912 KB Output is correct
21 Correct 33 ms 1912 KB Output is correct
22 Correct 36 ms 1952 KB Output is correct
23 Correct 1970 ms 60960 KB Output is correct
24 Correct 1226 ms 61160 KB Output is correct
25 Correct 1125 ms 61160 KB Output is correct
26 Correct 1010 ms 61160 KB Output is correct
27 Correct 1117 ms 61160 KB Output is correct
28 Correct 979 ms 61160 KB Output is correct
29 Correct 1103 ms 61160 KB Output is correct
30 Correct 1112 ms 61160 KB Output is correct
31 Correct 950 ms 61160 KB Output is correct
32 Correct 1079 ms 61184 KB Output is correct
33 Correct 81 ms 61184 KB Output is correct
34 Correct 234 ms 61184 KB Output is correct
35 Correct 868 ms 61184 KB Output is correct
36 Correct 1993 ms 61184 KB Output is correct
37 Correct 534 ms 61184 KB Output is correct
38 Correct 1753 ms 111776 KB Output is correct
39 Correct 1063 ms 111776 KB Output is correct
40 Correct 1149 ms 111776 KB Output is correct
41 Correct 1144 ms 111776 KB Output is correct
42 Correct 1254 ms 111776 KB Output is correct
43 Correct 958 ms 111776 KB Output is correct
44 Correct 77 ms 111776 KB Output is correct
45 Correct 135 ms 111776 KB Output is correct
46 Correct 173 ms 111776 KB Output is correct
47 Correct 219 ms 111776 KB Output is correct
48 Correct 327 ms 111776 KB Output is correct
49 Correct 1275 ms 111776 KB Output is correct
50 Correct 1255 ms 111776 KB Output is correct
51 Correct 828 ms 111776 KB Output is correct
52 Correct 2060 ms 111776 KB Output is correct
53 Correct 1200 ms 111776 KB Output is correct
54 Correct 1110 ms 111776 KB Output is correct
55 Correct 1133 ms 111776 KB Output is correct
56 Correct 238 ms 111776 KB Output is correct
57 Correct 465 ms 111776 KB Output is correct
58 Correct 685 ms 111776 KB Output is correct
59 Correct 1977 ms 111776 KB Output is correct
60 Correct 3135 ms 111776 KB Output is correct
61 Correct 1927 ms 111776 KB Output is correct
62 Correct 1189 ms 111776 KB Output is correct
63 Correct 2987 ms 111776 KB Output is correct
64 Correct 2076 ms 111776 KB Output is correct
65 Correct 1920 ms 111776 KB Output is correct
66 Correct 2398 ms 111776 KB Output is correct
67 Correct 1959 ms 111776 KB Output is correct
68 Correct 1510 ms 111776 KB Output is correct
69 Correct 2766 ms 111776 KB Output is correct