Submission #256840

#	Time	Username	Problem	Language	Result	Execution time	Memory
256840		Hehehe	Seats (IOI18_seats)	C++14	0 / 100	1304 ms	60700 KiB

seats

#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
#include "seats.h"

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const int N = 4000000 + 11;

pi t[4*N];
int lazy[4*N];
pi pos[4*N];
int tot, n, m;
vector<vector<int>>a;

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

pi tcombine(pi a, pi 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(lazy[n]){
        t[n].first += lazy[n];
        lazy[ln(n)] += lazy[n];
        lazy[rn(n)] += lazy[n];
        lazy[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){
        lazy[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)]);

}

bool ok(pi x){
    if(x.ff > 0 && x.ff <= n){
        if(x.ss > 0 && x.ss <= m){
            return 1;
        }
    }
    return 0;
}

pi getB(pi x){
    int l = a[x.ff][x.ss];
    int r = tot + 1;
    for(int i = 0; i < 4; i++){
        pi A = x;
        A.ff += dx[i];
        A.ss += dy[i];
        if(ok(A)){
            if(i < 2)r = min(r, a[x.ff][x.ss]);
        }
    }
    return {l, r};
}

int secondSmallestNeighbour(pi x){
    vector<int>s;

    for(int i = 0; i < 4; i++){
        pi A = x;
        A.ff += dx[i];
        A.ss += dy[i];
        if(ok(A)){
            s.push_back(a[A.ff][A.ss]);
        }
    }

    sort(all(s));

    if(sz(s) > 1)return s[1];
    return tot + 1;
}

void deleteA(pi x){
    int l = secondSmallestNeighbour(x);
    int r = a[x.ff][x.ss];
    if(r > l){
        update(1, 1, tot, l, r - 1, -1);
    }
}

void updateA(pi x){
    int l = secondSmallestNeighbour(x);
    int r = a[x.ff][x.ss];
    if(r > l){
        update(1, 1, tot, l, r - 1, +1);
    }
}

void deleteB(pi x){
    pi p = getB(x);
    if(p.ss > p.ff){
        update(1, 1, tot, p.ff, p.ss - 1, -1);
    }
}

void updateB(pi x){
    pi p = getB(x);
    if(p.ss > p.ff){
        update(1, 1, tot, p.ff, p.ss - 1, +1);
    }
}


void rewrite(pi x, int val){

    deleteA(x);
    for(int i = 0; i < 4; i++){
        pi A = x;
        A.ff += dx[i];
        A.ss += dy[i];
        if(ok(A)){
            deleteA(A);
        }
    }
    deleteB(x);
    for(int i = 2; i <  4; i++){
        pi A = x;
        A.ff += dx[i];
        A.ss += dy[i];
        if(ok(A)){
            deleteB(A);
        }
    }

    a[x.ff][x.ss] = val;

    updateA(x);
    for(int i = 0; i < 4; i++){
        pi A = x;
        A.ff += dx[i];
        A.ss += dy[i];
        if(ok(A)){
            updateA(A);
        }
    }
    updateB(x);
    for(int i = 2; i < 4; i++){
        pi A = x;
        x.ff += dx[i];
        x.ss += dy[i];
        if(ok(A)){
            updateB(A);
        }
    }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){

    m = W;
    n = H;

    tot = n*m;

    build(1, 1, tot);

    a = vector<vector<int>>(n + 5, vector<int>(m + 5, 0));

    for(int i = 0 ; i < n*m; i++){
        a[R[i] + 1][C[i] + 1] = i + 1;
        pos[i] = {R[i] + 1, C[i] + 1};
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            updateA({i, j}); //first condition
            updateB({i, j}); //second condition
        }
    }
}

int swap_seats(int A, int B) {

    rewrite(pos[A], B + 1);
    rewrite(pos[B], A + 1);

    swap(pos[A], pos[B]);

    return (t[1].ff == 1 ? t[1].ss : 0);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30