Submission #282062

#	Time	Username	Problem	Language	Result	Execution time	Memory
282062		doowey	Seats (IOI18_seats)	C++14	100 / 100	2660 ms	99652 KiB

seats

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "seats.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int M = (int)1e6 + 10;
int cur;
int pi[M], pj[M];
vector<vector<int>> tt;

int val[M * 4 + 512];
int cnt[M * 4 + 512];
int lazy[M * 4 + 512];


void push(int node, int cl, int cr){
    val[node] += lazy[node];
    if(cl != cr){
        lazy[node << 1] += lazy[node];
        lazy[node << 1 | 1] += lazy[node];
    }
    lazy[node] = 0;
}

void upd(int node, int cl, int cr, int tl, int tr, int x){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        lazy[node] = x;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) >> 1;
    upd(node << 1, cl, mid, tl, tr, x);
    upd(node << 1 | 1, mid + 1, cr, tl, tr, x);
    val[node] = val[node << 1];
    cnt[node] = cnt[node << 1];
    if(val[node << 1 | 1] == val[node]){
        cnt[node] += cnt[node << 1 | 1];
    }
    else if(val[node << 1 | 1] < val[node]){
        val[node] = val[node << 1 | 1];
        cnt[node] = cnt[node << 1 | 1];
    }
}

void upd_rect(int i, int j, int v){
    vector<int> tc;
    for(int p = 0; p < 2; p ++ ){
        for(int q = 0; q < 2; q ++ ){
            tc.push_back(tt[i + p][j + q]);
        }
    }
    sort(tc.begin(), tc.end());
    if(tc[0] < tc[1])
        upd(1, 0, cur - 1, tc[0], tc[1] - 1, v);
    if(tc[2] < tc[3])
        upd(1, 0, cur - 1, tc[2], tc[3] - 1, 4 * v);
}


int pf[M];

void build(int node, int cl, int cr){
    if(cl == cr){
        cnt[node] = 1;
        val[node] = pf[cl];
        return;
    }
    int mid = (cl + cr) >> 1;
    build(node << 1, cl, mid);
    build(node << 1 | 1, mid + 1, cr);
    val[node] = val[node << 1];
    cnt[node] = cnt[node << 1];
    if(val[node << 1 | 1] == val[node]){
        cnt[node] += cnt[node << 1 | 1];
    }
    else if(val[node << 1 | 1] < val[node]){
        val[node] = val[node << 1 | 1];
        cnt[node] = cnt[node << 1 | 1];
    }
}



void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    cur = H * W;
    tt.resize(H + 2);
    for(int i = 0 ; i <= H + 1;i ++ )
        tt[i].resize(W + 2, cur);
    for(int i = 0 ; i < cur ;i ++ ){
        R[i] ++ ;
        C[i] ++ ;
        pi[i] = R[i];
        pj[i] = C[i];
        tt[R[i]][C[i]] = i;
    }
    for(int i = 0 ; i <= H; i ++ ){
        for(int j = 0 ; j <= W; j ++ ){
            vector<int> pq;
            for(int l = 0; l < 2; l ++ ){
                for(int r = 0; r < 2; r ++ ){
                    pq.push_back(tt[i + l][j + r]);
                }
            }
            sort(pq.begin(), pq.end());
            pf[pq[0]] ++ ;
            pf[pq[1]] -- ;
            pf[pq[2]] += 4 ;
            pf[pq[3]] -= 4 ;
        }
    }
    for(int i = 1; i < cur; i ++ ){
        pf[i] += pf[i - 1];
    }
    build(1, 0, cur - 1);
}

int swap_seats(int a, int b) {
    vector<pii> nigs;
    for(int i = 0; i <= 1; i ++ ){
        for(int j = 0; j <= 1 ; j ++ ){
            nigs.push_back(mp(pi[a] - i, pj[a] - j));
            nigs.push_back(mp(pi[b] - i, pj[b] - j));
        }
    }
    sort(nigs.begin(), nigs.end());
    nigs.resize(unique(nigs.begin(), nigs.end()) - nigs.begin());
    for(auto x : nigs)
        upd_rect(x.fi, x.se, -1);
    swap(tt[pi[a]][pj[a]], tt[pi[b]][pj[b]]);
    swap(pi[a], pi[b]);
    swap(pj[a], pj[b]);
    for(auto x : nigs)
        upd_rect(x.fi, x.se, +1);
    return cnt[1];
}

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