Submission #256734

#	Time	Username	Problem	Language	Result	Execution time	Memory
256734		Hehehe	Seats (IOI18_seats)	C++14	0 / 100	458 ms	89740 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 ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 4000000 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

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

pi merge(pi a, pi 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 v){
    if(!lazy[v])return;

    t[v].ff += lazy[v];
    lazy[2*v] += lazy[v];
    lazy[2*v + 1] += lazy[v];
    lazy[v] = 0;
}

void build(int v, int l, int r){
    if(l == r){
        t[v] = {0, 1};
        return;
    }
    int mid = (l + r) >> 1;
    build(2*v, l, mid);
    build(2*v + 1, mid + 1, r);

    t[v] = merge(t[2*v], t[2*v + 1]);
}

void update(int v, int tl, int tr, int l, int r, int add){
    push(v);
    
    if(l > r)return;

    if(l <= tl && tr <= r){
        lazy[v] += add;
        push(v);
        return;
    }

    int mid = (l + r) >> 1;

    if(l <= mid)update(2*v, tl, mid, l, r, add);
    if(r > mid)update(2*v + 1, mid + 1, tr, l, r, add);

    push(2*v);
    push(2*v + 1);

    t[v] = merge(t[2*v], t[2*v + 1]);

}

bool ok(int x, int y){
    if(x < 0 || x > n || y < 0 || y > m)return 0;
    return 1;
}

pi getmin(pi x){

    int mn = tot + 1;

    for(int i = 0; i < 2; i++){
        int X = x.ff + dx[i];
        int Y = x.ss + dy[i];
        if(ok(X,Y))mn = min(mn, a[X][Y]);
    }

    return {a[x.ff][x.ss], mn};
}

int secondSmallestNeighbourA(pi x){

    vector<int>vec;

    for(int i = 0; i < 4; i++){
        int X = x.ff + dx[i];
        int Y = x.ss + dy[i];
        if(ok(X,Y))vec.push_back(a[X][Y]);
    }

    sort(all(vec));

    if(sz(vec) <= 1)return tot + 1;
    return vec[1];
}

void updateA(pi x){
    int l = secondSmallestNeighbourA(x);
    int r = a[x.ff][x.ss];
    if(r > l){
        update(1, 1, n*m, l, r - 1, 1);
    }
}

void updateB(pi x){
    pi cur = getmin(x);
    if(cur.ss > cur.ff){
        update(1, 1, n*m, cur.ff, cur.ss - 1, 1);
    }
}

void deleteB(pi x){
    pi cur = getmin(x);
    if(cur.ss > cur.ff){
        update(1, 1, n*m, cur.ff, cur.ss - 1, -1);
    }
}

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

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

    m = W;
    n = H;

    tot = n*m;

    build(1, 1, n*m);

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

void rewrite(pi x, int val){return;


    deleteA(x);
    for(int i = 0; i < 4; i++){
        int X = dx[i] + x.ff;
        int Y = dy[i] + x.ss;
        if(ok(X, Y)){
            deleteA({X, Y});
        }
    }

    deleteB(x);
    for(int i = 2; i < 4; i++){
        int X = dx[i] + x.ff;
        int Y = dy[i] + x.ss;
        if(ok(X, Y)){
            deleteB({X, Y});
        }
    }

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

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

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