Submission #81209

#	Time	Username	Problem	Language	Result	Execution time	Memory
81209		cki86201	Seats (IOI18_seats)	C++11	100 / 100	3874 ms	77716 KiB

seats

#include "seats.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int T[1<<21], A[1<<21], cnt[1<<21];
int R[1000010], C[1000010];
int N, M, P;

void init(int rt, int l, int r) {
    cnt[rt] = r - l + 1;
    if(l == r) return;
    int m = (l + r) >> 1;
    init(rt<<1, l, m);
    init(rt<<1|1, m+1, r);
}

inline void pushup(int rt) {
    if(T[rt<<1] == T[rt<<1|1]) cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1], T[rt] = T[rt<<1];
    else if(T[rt<<1] < T[rt<<1|1]) cnt[rt] = cnt[rt<<1], T[rt] = T[rt<<1];
    else cnt[rt] = cnt[rt<<1|1], T[rt] = T[rt<<1|1];
}

void add(int rt, int l, int r, int s, int e, int c) {
    if(s <= l && r <= e) {
        T[rt] += c;
        A[rt] += c;
        return;
    }
    if(A[rt]) {
        T[rt<<1] += A[rt];
        A[rt<<1] += A[rt];
        T[rt<<1|1] += A[rt];
        A[rt<<1|1] += A[rt];
        A[rt] = 0;
    }
    int m = (l + r) >> 1;
    if(s <= m) add(rt<<1, l, m, s, e, c);
    if(m < e) add(rt<<1|1, m+1, r, s, e, c);
    pushup(rt);
}

void add(int l, int r, int v) {
    add(1, 1, P, l, r, v);
}

int rval[1000010];

void get_val(int x, int y, int rr[]) {
    int rz = 0;
    for(int dx : {0,1}) for(int dy : {0,1}) {
        int ni = x + dx, nj = y + dy, val = P + 1;
        if(1 <= ni && ni <= N && 1 <= nj && nj <= M) {
            val = rval[(ni-1)*M+(nj-1)];
        }
        rr[rz++] = val;
    }
    sort(rr, rr+4);
}

void give_initial_chart(int H, int W, std::vector<int> tR, std::vector<int> tC) {
    N = H; M = W;
    P = N * M;
    init(1, 1, P);
    rep(i, P) R[i + 1] = tR[i] + 1, C[i + 1] = tC[i] + 1;
    for(int i=1;i<=P;i++) rval[(R[i]-1)*M+(C[i]-1)] = i;
    rep(i, N+1) rep(j, M+1) {
        int tt[4];
        get_val(i, j, tt);
        if(tt[0]<tt[1]) add(tt[0], tt[1]-1, 1);
        if(tt[2]<tt[3]) add(tt[2], tt[3]-1, 100);
    }
}

void change(int r, int c, int x) {
    for(int dx:{-1,0}) for(int dy:{-1,0}) {
        int tt[4];
        get_val(r+dx, c+dy, tt);
        if(tt[0]<tt[1]) add(tt[0], tt[1]-1, -1);
        if(tt[2]<tt[3]) add(tt[2], tt[3]-1, -100);
    }
    rval[(r-1)*M+(c-1)] = x;
    for(int dx:{-1,0}) for(int dy:{-1,0}) {
        int tt[4];
        get_val(r+dx, c+dy, tt);
        if(tt[0]<tt[1]) add(tt[0], tt[1]-1, 1);
        if(tt[2]<tt[3]) add(tt[2], tt[3]-1, 100);
    }
}

int swap_seats(int a, int b) {
    ++a; ++b;
    change(R[a], C[a], b);
    change(R[b], C[b], a);
    swap(R[a], R[b]);
    swap(C[a], C[b]);
    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