Submission #297109

#	Time	Username	Problem	Language	Result	Execution time	Memory
297109		Aldas25	Seats (IOI18_seats)	C++14	17 / 100	4035 ms	52908 KiB

seats

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1,(n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> pii;

vi r, c;
int h, w, n;

//vector<bool> checked;
map<pii, int> id;

/*vi par, sz, minR, maxR, minC, maxC;
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
bool same (int a, int b) {return find(a) == find(b);}
void unite (int a, int b){
    a = find(a), b = find(b);
    if (a == b) return;
    par[b] = a;
    sz[a] += sz[b];
    minR[a] = min (minR[a], minR[b]);
    minC[a] = min (minC[a], minC[b]);
    maxR[a] = max (maxR[a], maxR[b]);
    maxC[a] = max (maxC[a], maxC[b]);
}*/
vi minR, maxR, minC, maxC;

/*void resetDSU () {
    FOR(i, 0, n-1) {
        par[i] = i;
        sz[i] = 1;
        minR[i] = maxR[i] = r[i];
        minC[i] = maxC[i] = c[i];
    }
}*/

int ans = 0;

bool check (int i) {
    //int p = find(i);
    return (i+1) == (maxR[i] - minR[i] + 1) * (maxC[i] - minC[i] + 1);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    r = R;
    c = C;
    h = H;
    w = W;
    n = h*w;
    FOR(i, 0, n-1) {
        //par.pb(i);
        //sz.pb(1);
        minR.pb(r[i]);
        maxR.pb(r[i]);
        minC.pb(c[i]);
        maxC.pb(c[i]);

       // id[{r[i],c[i]}] = i+1;
    }

    FOR(i, 0, n-1) {
        if (i > 0) {
            maxR[i] = max (maxR[i], maxR[i-1]);
            maxC[i] = max(maxC[i], maxC[i-1]);
            minR[i] = min(minR[i], minR[i-1]);
            minC[i] = min(minC[i], minC[i-1]);
        }
        ans += check(i);
    }

    //FOR(i, 0, n-1) checked.pb(0);
}


int swap_seats(int a, int b) {
    if (a > b) swap(a,b);

    FOR(i, a, b) ans -= check(i);

    swap(r[a], r[b]);
    swap(c[a], c[b]);
    //resetDSU();
    //int ret = 0;
    FOR(i, a, b) {
        /*FOR(dx, -1, 1) FOR(dy, -1, 1) {
            int x = id[{r[i]+dx, c[i]+dy}];
            x--;
            if (x != -1 && x < i) unite(x, i);
        }*/
        //if (i > 0) unite(i, i-1);
        if (i > 0) {
            maxR[i] = max (r[i], maxR[i-1]);
            maxC[i] = max(c[i], maxC[i-1]);
            minR[i] = min(r[i], minR[i-1]);
            minC[i] = min(c[i], minC[i-1]);
        } else {
            maxR[i] = minR[i] = r[i];
            maxC[i] = minC[i] = c[i];
        }
        ans += check (i);
    }
    return ans;
}

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