Submission #1116655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116655		jkb_gryz	Seats (IOI18_seats)	C++14	100 / 100	3067 ms	151524 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"

using namespace std;

#define ll long long
#define para pair<ll, ll>

const int base = 1<<20;
const int MAXN = 1e6+7;
const int INF = 1e9;

para tree[base<<1];
ll lazy[base<<1];

void push(ll v, ll l, ll r){
    lazy[l] += lazy[v];
    lazy[r] += lazy[v];

    tree[l].first += lazy[v];
    tree[r].first += lazy[v];

    lazy[v] = 0;
}

ll p, k;
ll val;

void build(ll v, ll a, ll b){
    if(a == b){
        tree[v] = {0, 1};
    }
    else{
        ll mid = (a + b)/2, l = 2*v, r = 2*v+1;

        build(l, a, mid);
        build(r, mid+1, b);
    }
}

void update(ll v, ll a, ll b){
    if(a > k || b < p) return;  
    if(p <= a && k >= b){
        tree[v].first += val;
        lazy[v] += val;
        return;
    }

    ll mid = (a + b)/2, l = 2*v, r = 2*v+1;

    push(v, l, r);

    update(l, a, mid);
    update(r, mid+1, b);

    if(tree[l].first < tree[r].first) tree[v].second = tree[l].second;
    else if(tree[l].first > tree[r].first) tree[v].second = tree[r].second;
    else tree[v].second = tree[l].second + tree[r].second;

    tree[v].first = min(tree[l].first, tree[r].first);
}

para query(ll v, ll a, ll b){
    if(a > k || b < p) return {INF, 0};
    if(p <= a && k >= b){
        return tree[v];
    }
    
    ll mid = (a + b)/2, l = 2*v, r = 2*v+1;

    push(v, l, r);

    para ql = query(l, a, mid);
    para qr = query(r, mid+1, b);

    if(ql.first < qr.first) return ql;
    else if(ql.first > qr.first) return qr;
    else return {ql.first, ql.second + qr.second};
}

vector<vector<ll>> grid;
para poz[MAXN];

ll n;

vector<vector<para>> dir = {{{-1, 0}, {-1, -1}, {0, -1}}, {{-1, 0}, {-1, 1}, {0, 1}}, {{0, 1}, {1, 1}, {1, 0}}, {{1, 0}, {1, -1}, {0, -1}}};

void calc(para poz){
    for(auto d : dir){
        vector<ll> tmp = {grid[poz.first][poz.second]};
        for(auto j : d){
            tmp.push_back(grid[poz.first+j.first][poz.second+j.second]);
        }
        sort(tmp.begin(), tmp.end());
        // cerr << tmp[0] << "-" << tmp[1]-1 << ", " << tmp[2] << "-" << tmp[3]-1 << "\n";
        p = tmp[0], k = tmp[1]-1;
        update(1, 1, n+7);
        p = tmp[2], k = tmp[3]-1;
        update(1, 1, n+7);
    }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n = H*W;
    grid = vector<vector<ll>> (H+2, vector<ll> (W+2, n+1));

    build(1, 1, n+7);
    for(int i = 0; i < H*W; ++i){
        poz[i+1] = {R[i]+1, C[i]+1};
        grid[R[i]+1][C[i]+1] = i+1;
    }

    val = 1;
    for(int i = 0; i <= H; ++i){
        for(int j = 0; j <= W; ++j){
            vector<ll> tmp = {grid[i][j], grid[i+1][j], grid[i][j+1], grid[i+1][j+1]};
            sort(tmp.begin(), tmp.end());
            p = tmp[0], k = tmp[1]-1;
            update(1, 1, n+7);
            p = tmp[2], k = tmp[3]-1;
            update(1, 1, n+7);
        }   
    }    

    // for(int i = 1; i <= n; ++i){
    //     p = k = i;
    //     cerr << query(1, 1, n+7).first << " ";
    // }
    // cerr << "\n";
}

int swap_seats(int a, int b){
    ++a;
    ++b;
    val = -1;
    calc(poz[a]);
    // for(int i = 1; i <= n; ++i){
    //     p = k = i;
    //     cerr << query(1, 1, n+7).first << " ";
    // }
    // cerr << "\n";
    calc(poz[b]);
    
    // for(int i = 1; i <= n; ++i){
    //     p = k = i;
    //     cerr << query(1, 1, n+7).first << " ";
    // }
    // cerr << "\n";
    swap(poz[a], poz[b]);
    swap(grid[poz[a].first][poz[a].second], grid[poz[b].first][poz[b].second]);

    val = 1;
    calc(poz[a]);
    calc(poz[b]);

    // for(int i = 1; i <= n; ++i){
    //     p = k = i;
    //     cerr << query(1, 1, n+7).first << " ";
    // }
    // cerr << "\n";

    p = 1, k = n;
    return query(1, 1, n+7).second;
}

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