Submission #788906

#	Time	Username	Problem	Language	Result	Execution time	Memory
788906		lukameladze	Seats (IOI18_seats)	C++17	70 / 100	4086 ms	135628 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 1e6 + 5, inf = 1e9;
int r[N], c[N],all;
int n,m;
vector <vector <int> > a; // map ?
struct nod {
    int mnf, mns, cnt;
};
nod tree[4 * N];
int lazy[2][4 * N];
nod merge(nod a, nod b) {
    if (a.mnf != b.mnf) {
        return (a.mnf < b.mnf ? a : b);
    }
    if (a.mns != b.mns) {
        return (a.mns < b.mns ? a : b);
    }
    return {a.mnf, a.mns, a.cnt + b.cnt};
}
void build(int node, int le, int ri) {
    if (le == ri) {
        tree[node] = {0, 0, 1};
        return ;
    }
    int mid = (le + ri) / 2;
    build(2 * node, le, mid);
    build(2 * node + 1, mid + 1, ri);
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
void push(int node, int le, int ri) {
    if (!lazy[0][node] && !lazy[1][node]) return ;
    tree[node].mnf += lazy[0][node];
    tree[node].mns += lazy[1][node];
    if (le != ri) {
        for (int ty = 0; ty < 2; ty++) {
            lazy[ty][2 * node] += lazy[ty][node];
            lazy[ty][2 * node + 1] += lazy[ty][node];
        }
    }
    lazy[0][node] = lazy[1][node] = 0;
}
void update(int node, int le, int ri, int start, int end, int val, int ty) {
    push(node, le, ri);
    if (le > end || ri < start) return ;
    if (le >= start && ri <= end) {
        lazy[ty][node] = val;
        push(node, le, ri);
        return ;
    }
    int mid = (le + ri) >> 1;
    update(2 * node, le, mid,start, end, val, ty);
    update(2 * node + 1, mid + 1, ri, start, end, val, ty);
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
nod getans(int node, int le, int ri, int start, int end) {
    push(node, le, ri);
    if (le > end || ri < start) return {inf, inf, 0};
    if (le >= start && ri <= end) {
        return tree[node];
    }
    int mid = (le + ri) >> 1;
    return merge(getans(2 * node, le, mid, start, end), getans(2 * node + 1, mid + 1, ri, start, end));
}
void upd(int l, int r, int vl, int ty) {
    update(1, 1, all, l, r, vl, ty);
}
void add(int i, int j, int vl) {
    vector <int> vec;
    vec.pb(a[i][j]); vec.pb(a[i + 1][j]); vec.pb(a[i][j + 1]); vec.pb(a[i + 1][j + 1]);
    sort(vec.begin(), vec.end());
    if (vec[0] < vec[1]) upd(vec[0], vec[1] - 1, vl, 0);
    if (vec[2] < vec[3]) upd(vec[2], vec[3] - 1, vl, 1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H; m = W;
    a = vector < vector <int> > (n + 5, vector <int> (m + 5, 0));
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            a[i][j] = n * m + 1;
        }
    }
    all = n * m;
    for (int i = 0; i < n * m; i++) {
        r[i + 1] = R[i] + 1; c[i + 1] = C[i] + 1;
        a[r[i + 1]][c[i + 1]] = i + 1;
    }

    build(1, 1, all);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            // {i, j}   {i + 1, j}   {i, j + 1}   {i + 1, j + 1}
            add(i, j, 1);
        }
    }
//    for (int i = 1; i <= n * m; i++) {
//        cout<<i<<" ->  "<<getans(1, 1, all, i, i).mnf<<" "<<getans(1 ,1, all, i, i).mns<<" "<<getans(1, 1, all, i, i).cnt<<"\n";
//    }
//    cout<<tree[1].mnf<<" "<<tree[1].mns<<"\n";
//    if (tree[1].mnf == 4 && tree[1].mns == 0) {
//        cout<<tree[1].cnt<<"\n";
//    }
}

int swap_seats(int x, int y) {
    // {r[x], c[x]} --- >
    x++; y++;
//    cout<<"was "<<tree[1].mnf<<"   "<<tree[1].mns<<"\n";
    for (int ii = 0; ii < 2; ii++) {
        int pos = (ii == 0 ? x : y);
        for (int i = r[pos] - 1; i <= r[pos]; i++) {
            for (int j = c[pos] - 1; j <= c[pos]; j++) {
                add(i, j, -1);
            }
        }
    }
    a[r[x]][c[x]] = y;
    a[r[y]][c[y]] = x;
    swap(r[x], r[y]); swap(c[x], c[y]);

    for (int ii = 0; ii < 2; ii++) {
        int pos = (ii == 0 ? x : y);
        for (int i = r[pos] - 1; i <= r[pos]; i++) {
            for (int j = c[pos] - 1; j <= c[pos]; j++) {
                add(i, j, 1);
            }
        }
    }
    if (tree[1].mnf == 4 && tree[1].mns == 0) {
        return tree[1].cnt;
    } else return 0;
}

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