oj.uz

Submission #256843

# Submission time Handle Problem Language Result Execution time Memory
256843 2020-08-03T09:40:35 Z Hehehe Seats (IOI18_seats) C++14
100 / 100
 2580 ms 115576 KB 
#include "seats.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define ff first
#define ss second
using namespace std;
const int NMAX = 4000005;

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

typedef pair<int, int> pii;

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

void updateA(pii pos);
void deleteA(pii pos);
void updateB(pii pos);
void deleteB(pii pos);
int secondSmallestNeighbour(pii pos);
pii getB(pii pos);
bool ok(pii pos);
void addInterval(int l, int r);
void subInterval(int l, int r);
void rewrite(pii pos, int val);

vector<vector<int>> arr;

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

pii merge(pii a, pii b){
    if(a.ff < b.ff)return a;
    if(a.ff > b.ff)return b;
    return {a.ff, a.ss + b.ss};
}

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] = merge(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] = merge(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;
    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){
            updateA({i, j});
            updateB({i, j});
        }
    }

}

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

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

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


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

void rewrite(pii pos, int val){

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

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

    updateA(pos);
    for(int i=0; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(ok(aux)){
            updateA(aux);
        }
    }
    updateB(pos);
    for(int i=2; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(ok(aux)){
            updateB(aux);
        }
    }
}


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

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

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

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

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

pii getB(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(ok(aux)){
            if(i < 2)
                r = min(r, arr[aux.x][aux.y]);
        }
    }
    return {l, r};
}

bool ok(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){
    update(1, 1, tsz, l, r, +1);
}

void subInterval(int l, int r){
    update(1, 1, tsz, l, r, -1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 512 KB Output is correct
2 Correct 30 ms 512 KB Output is correct
3 Correct 40 ms 512 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 16 ms 512 KB Output is correct
6 Correct 31 ms 512 KB Output is correct
7 Correct 36 ms 504 KB Output is correct
8 Correct 36 ms 512 KB Output is correct
9 Correct 41 ms 632 KB Output is correct
10 Correct 36 ms 512 KB Output is correct
11 Correct 32 ms 512 KB Output is correct
12 Correct 16 ms 512 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 512 KB Output is correct
2 Correct 30 ms 512 KB Output is correct
3 Correct 40 ms 512 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 16 ms 512 KB Output is correct
6 Correct 31 ms 512 KB Output is correct
7 Correct 36 ms 504 KB Output is correct
8 Correct 36 ms 512 KB Output is correct
9 Correct 41 ms 632 KB Output is correct
10 Correct 36 ms 512 KB Output is correct
11 Correct 32 ms 512 KB Output is correct
12 Correct 16 ms 512 KB Output is correct
13 Correct 74 ms 1388 KB Output is correct
14 Correct 75 ms 1400 KB Output is correct
15 Correct 36 ms 1408 KB Output is correct
16 Correct 31 ms 1912 KB Output is correct
17 Correct 51 ms 1408 KB Output is correct
18 Correct 62 ms 1400 KB Output is correct
19 Correct 54 ms 1408 KB Output is correct
20 Correct 38 ms 1536 KB Output is correct
21 Correct 28 ms 1408 KB Output is correct
22 Correct 29 ms 1912 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1667 ms 62072 KB Output is correct
2 Correct 1097 ms 64632 KB Output is correct
3 Correct 977 ms 64632 KB Output is correct
4 Correct 887 ms 62588 KB Output is correct
5 Correct 984 ms 64632 KB Output is correct
6 Correct 906 ms 62760 KB Output is correct
7 Correct 939 ms 64760 KB Output is correct
8 Correct 979 ms 62732 KB Output is correct
9 Correct 871 ms 64632 KB Output is correct
10 Correct 972 ms 64760 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 1408 KB Output is correct
2 Correct 159 ms 8312 KB Output is correct
3 Correct 843 ms 64120 KB Output is correct
4 Correct 1644 ms 64776 KB Output is correct
5 Correct 507 ms 59932 KB Output is correct
6 Correct 1532 ms 115576 KB Output is correct
7 Correct 933 ms 65632 KB Output is correct
8 Correct 1032 ms 65016 KB Output is correct
9 Correct 948 ms 63224 KB Output is correct
10 Correct 1058 ms 69640 KB Output is correct
11 Correct 880 ms 86264 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2036 KB Output is correct
2 Correct 119 ms 2164 KB Output is correct
3 Correct 156 ms 2164 KB Output is correct
4 Correct 183 ms 2164 KB Output is correct
5 Correct 276 ms 2932 KB Output is correct
6 Correct 1049 ms 63024 KB Output is correct
7 Correct 1139 ms 65328 KB Output is correct
8 Correct 795 ms 58292 KB Output is correct
9 Correct 1741 ms 64948 KB Output is correct
10 Correct 1018 ms 63920 KB Output is correct
11 Correct 954 ms 64056 KB Output is correct
12 Correct 985 ms 63036 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 512 KB Output is correct
2 Correct 30 ms 512 KB Output is correct
3 Correct 40 ms 512 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 16 ms 512 KB Output is correct
6 Correct 31 ms 512 KB Output is correct
7 Correct 36 ms 504 KB Output is correct
8 Correct 36 ms 512 KB Output is correct
9 Correct 41 ms 632 KB Output is correct
10 Correct 36 ms 512 KB Output is correct
11 Correct 32 ms 512 KB Output is correct
12 Correct 16 ms 512 KB Output is correct
13 Correct 74 ms 1388 KB Output is correct
14 Correct 75 ms 1400 KB Output is correct
15 Correct 36 ms 1408 KB Output is correct
16 Correct 31 ms 1912 KB Output is correct
17 Correct 51 ms 1408 KB Output is correct
18 Correct 62 ms 1400 KB Output is correct
19 Correct 54 ms 1408 KB Output is correct
20 Correct 38 ms 1536 KB Output is correct
21 Correct 28 ms 1408 KB Output is correct
22 Correct 29 ms 1912 KB Output is correct
23 Correct 1667 ms 62072 KB Output is correct
24 Correct 1097 ms 64632 KB Output is correct
25 Correct 977 ms 64632 KB Output is correct
26 Correct 887 ms 62588 KB Output is correct
27 Correct 984 ms 64632 KB Output is correct
28 Correct 906 ms 62760 KB Output is correct
29 Correct 939 ms 64760 KB Output is correct
30 Correct 979 ms 62732 KB Output is correct
31 Correct 871 ms 64632 KB Output is correct
32 Correct 972 ms 64760 KB Output is correct
33 Correct 74 ms 1408 KB Output is correct
34 Correct 159 ms 8312 KB Output is correct
35 Correct 843 ms 64120 KB Output is correct
36 Correct 1644 ms 64776 KB Output is correct
37 Correct 507 ms 59932 KB Output is correct
38 Correct 1532 ms 115576 KB Output is correct
39 Correct 933 ms 65632 KB Output is correct
40 Correct 1032 ms 65016 KB Output is correct
41 Correct 948 ms 63224 KB Output is correct
42 Correct 1058 ms 69640 KB Output is correct
43 Correct 880 ms 86264 KB Output is correct
44 Correct 78 ms 2036 KB Output is correct
45 Correct 119 ms 2164 KB Output is correct
46 Correct 156 ms 2164 KB Output is correct
47 Correct 183 ms 2164 KB Output is correct
48 Correct 276 ms 2932 KB Output is correct
49 Correct 1049 ms 63024 KB Output is correct
50 Correct 1139 ms 65328 KB Output is correct
51 Correct 795 ms 58292 KB Output is correct
52 Correct 1741 ms 64948 KB Output is correct
53 Correct 1018 ms 63920 KB Output is correct
54 Correct 954 ms 64056 KB Output is correct
55 Correct 985 ms 63036 KB Output is correct
56 Correct 217 ms 2036 KB Output is correct
57 Correct 400 ms 2164 KB Output is correct
58 Correct 553 ms 3260 KB Output is correct
59 Correct 1710 ms 61308 KB Output is correct
60 Correct 2580 ms 61176 KB Output is correct
61 Correct 1583 ms 59128 KB Output is correct
62 Correct 1094 ms 56252 KB Output is correct
63 Correct 2447 ms 62540 KB Output is correct
64 Correct 1710 ms 61424 KB Output is correct
65 Correct 1589 ms 61216 KB Output is correct
66 Correct 1834 ms 61176 KB Output is correct
67 Correct 1728 ms 65912 KB Output is correct
68 Correct 1361 ms 75000 KB Output is correct
69 Correct 2305 ms 84728 KB Output is correct