제출 #1285472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285472		mariaclara	자리 배치 (IOI18_seats)	C++20	100 / 100	1824 ms	180648 KiB

seats

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, m;
vector<vi> V, modd;
vector<pii> seg;
vi lazy, r, c;

pii operator + (pii a, pii b) {
    if(a.fr == b.fr) return {a.fr, a.sc + b.sc};
    return min(a, b);
}

void prop(int node, int flag) {
    if(!lazy[node]) return;

    seg[node].fr += lazy[node];

    if(flag) {
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
    }

    lazy[node] = 0;
}

void update(int node, int l, int r, int p, int q, int val) {
    prop(node, l!=r);

    if(r < p or q < l) return;
    if(p <= l and r <= q) {
        lazy[node] += val;
        prop(node, l!=r);
        return;
    }

    int mid = (l+r)/2;
    update(2*node, l, mid, p, q, val);
    update(2*node+1, mid+1, r, p, q, val);

    seg[node] = seg[2*node] + seg[2*node+1];
}

int count_9(int t[3][3]) {
    int cnt = 0;
    cnt += (t[0][0] + t[0][1] + t[1][0] + t[1][1])%2;
    cnt += (t[0][1] + t[0][2] + t[1][1] + t[1][2])%2;
    cnt += (t[1][0] + t[1][1] + t[2][0] + t[2][1])%2;
    cnt += (t[1][1] + t[1][2] + t[2][1] + t[2][2])%2;
    return cnt;
}

void set_value(int x, int y, int value, int flag) {
    if(x <= 0 or y <= 0 or n < x or m < y) return;

    int p1[3][3], p2[3][3]; // gerar duas matrizes 3x3

    V[x][y] = value;

    for(int i = -1; i <= 1; i++) {
        for(int j = -1; j <= 1; j++) {
            p1[i+1][j+1] = V[x+i][y+j] < value;
            p2[i+1][j+1] = V[x+i][y+j] <= value;
        }
    }
    
    int A = count_9(p2), B = count_9(p1);
    update(1, 0, n*m-1, value, n*m-1, flag*(A-B));
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n = H; m = W; 

    V.resize(n+2, vi(m+2, 1e9));
    modd.resize(n+2, vi(m+2));
    seg.resize(4*n*m, mk(0,1));
    lazy.resize(4*n*m);

    for(int i = 0; i < R.size(); i++) {
        R[i]++; C[i]++;
        V[R[i]][C[i]] = i;
    }
    
    r = R; c = C;

    for(int x = 1; x <= n; x++)
        for(int y = 1; y <= m; y++)
            set_value(x, y, V[x][y], 1);
}

int swap_seats(int a, int b) {
    for(int i = -1; i <= 1; i++) {
        for(int j = -1; j <= 1; j++) {
            if(modd[r[a]+i][c[a]+j] == 0) set_value(r[a]+i, c[a]+j, V[r[a]+i][c[a]+j], -1);
            modd[r[a]+i][c[a]+j] = 1;
            if(modd[r[b]+i][c[b]+j] == 0) set_value(r[b]+i, c[b]+j, V[r[b]+i][c[b]+j], -1);
            modd[r[b]+i][c[b]+j] = 1;
        }
    }

    swap(V[r[a]][c[a]], V[r[b]][c[b]]);
    swap(r[a], r[b]);
    swap(c[a], c[b]);

    for(int i = -1; i <= 1; i++) {
        for(int j = -1; j <= 1; j++) {
            if(modd[r[a]+i][c[a]+j] == 1) set_value(r[a]+i, c[a]+j, V[r[a]+i][c[a]+j], 1);
            modd[r[a]+i][c[a]+j] = 0;
            if(modd[r[b]+i][c[b]+j] == 1) set_value(r[b]+i, c[b]+j, V[r[b]+i][c[b]+j], 1);
            modd[r[b]+i][c[b]+j] = 0;
        }
    }

    return seg[1].sc;
}

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