Submission #119432

#	Time	Username	Problem	Language	Result	Execution time	Memory
119432		songc	Seats (IOI18_seats)	C++14	20 / 100	4034 ms	77192 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int H, W;
int R[1010101];
int C[1010101];
vector<vector<int>> M;
pii CV[4040404], lazy[4040404];
int cnt[4040404];

void init(int id, int s, int e){
    cnt[id] = e-s+1;
    if (s == e) return;
    int mid = (s+e)/2;
    init(id*2, s, mid);
    init(id*2+1, mid+1, e);
}

pii operator+(pii a, pii b){
    return pii(a.first+b.first, a.second+b.second);
}

void update(int id, int s, int e, int ts, int te, pii cv){
    if (e < ts || te < s) return;

    if (ts <= s && e <= te){
        CV[id] = CV[id] + cv;
        lazy[id] = lazy[id] + cv;
        return;
    }

    int mid = (s+e)/2;
    CV[id*2] = CV[id*2] + lazy[id];
    CV[id*2+1] = CV[id*2+1] + lazy[id];
    lazy[id*2] = lazy[id*2] + lazy[id], lazy[id*2+1] = lazy[id*2+1] + lazy[id];
    lazy[id] = pii(0, 0);

    update(id*2, s, mid, ts, te, cv);
    update(id*2+1, mid+1, e, ts, te, cv);
    if (CV[id*2] < CV[id*2+1]) CV[id] = CV[id*2], cnt[id] = cnt[id*2];
    else if (CV[id*2] > CV[id*2+1]) CV[id] = CV[id*2+1], cnt[id] = cnt[id*2+1];
    else CV[id] = CV[id*2], cnt[id] = cnt[id*2] + cnt[id*2+1];
}

void angle(int x, int y, int v){
    vector<int> t;
    t.push_back(M[x][y]); t.push_back(M[x][y+1]);
    t.push_back(M[x+1][y]); t.push_back(M[x+1][y+1]);
    sort(t.begin(), t.end());
    update(1, 1, H*W, t[0], t[1]-1, pii(v, 0));
    if ((t[0] == M[x][y] && t[1] == M[x+1][y+1]) || (t[1] == M[x][y] && t[0] == M[x+1][y+1])
    || (t[0] == M[x+1][y] && t[1] == M[x][y+1]) || (t[1] == M[x+1][y] && t[0] == M[x][y+1])){
        update(1, 1, H*W, t[1], t[2]-1, pii(0, 2*v));
    }
    update(1, 1, H*W, t[2], t[3]-1, pii(0, v));
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
    H=h, W=w;
    M.reserve(H+2);
    init(1, 1, H*W);
    for (int i=0; i<=H+1; i++) M[i].reserve(W+2);
    for (int i=0; i<=W+1; i++) M[0][i] = M[H+1][i] = H*W+1;
    for (int i=0; i<=H+1; i++) M[i][0] = M[i][W+1] = H*W+1;
    for (int i=1; i<=H*W; i++){
        R[i] = r[i-1]+1, C[i] = c[i-1]+1;
        M[R[i]][C[i]] = i;
    }
    for (int i=0; i<=H; i++) for (int j=0; j<=W; j++) {
        angle(i, j, 1);
    }
}

int swap_seats(int a, int b) {
    a++, b++;
    angle(R[a]-1, C[a]-1, -1);
    angle(R[a], C[a]-1, -1);
    angle(R[a]-1, C[a], -1);
    angle(R[a], C[a], -1);

    angle(R[b]-1, C[b]-1, -1);
    angle(R[b], C[b]-1, -1);
    angle(R[b]-1, C[b], -1);
    angle(R[b], C[b], -1);

    swap(R[a], R[b]); swap(C[a], C[b]);
    M[R[a]][C[a]] = a;
    M[R[b]][C[b]] = b;

    angle(R[a]-1, C[a]-1, 1);
    angle(R[a], C[a]-1, 1);
    angle(R[a]-1, C[a], 1);
    angle(R[a], C[a], 1);

    angle(R[b]-1, C[b]-1, 1);
    angle(R[b], C[b]-1, 1);
    angle(R[b]-1, C[b], 1);
    angle(R[b], C[b], 1);
    return cnt[1];
}

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