Submission #1285479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285479		mariaclara	Seats (IOI18_seats)	C++20	100 / 100	1477 ms	129624 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;
vector<pii> seg;
vi lazy, r, c, modd;

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;
}

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

    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;
        }
    }
    
    return count_9(p2) - count_9(p1);
}

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, n*m));
    modd.resize(n*m+1);
    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++) {
            update(1, 0, n*m-1, V[x][y], n*m-1, set_value(x, y, V[x][y]));
        }
    }
}

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

    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[V[r[a]+i][c[a]+j]] != 0 and V[r[a]+i][c[a]+j] != n*m) {
                int ch = set_value(r[a]+i, c[a]+j, V[r[a]+i][c[a]+j]);
                ch -= modd[V[r[a]+i][c[a]+j]] - 10;
                update(1, 0, n*m-1, V[r[a]+i][c[a]+j], n*m-1, ch);
            }
            if(modd[V[r[b]+i][c[b]+j]] != 0 and V[r[b]+i][c[b]+j] != n*m) {
                int ch = set_value(r[b]+i, c[b]+j, V[r[b]+i][c[b]+j]);
                ch -= modd[V[r[b]+i][c[b]+j]] - 10;
                update(1, 0, n*m-1, V[r[b]+i][c[b]+j], n*m-1, ch);
            }
            modd[V[r[a]+i][c[a]+j]] = 0;
            modd[V[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