Submission #138873

#	Time	Username	Problem	Language	Result	Execution time	Memory
138873		Nnandi	Seats (IOI18_seats)	C++14	17 / 100	4112 ms	188764 KiB

seats

#include<bits/stdc++.h>
#include "seats.h"
using namespace std;

const int maxn = 1000005;
const int INF = INT_MAX - 1;
int jo[maxn];

struct Elem {
    int h_max, h_min;
    int w_max, w_min;
    bool ures;
    Elem() {
        ures = true;
        h_max = -1;
        h_min = INF;
        w_max = -1;
        w_min = INF;
    }
    Elem(int x, int y) {
        ures = false;
        h_max = x;
        h_min = x;
        w_max = y;
        w_min = y;
    }
    void rep(Elem a, Elem b) {
        ures = a.ures && b.ures;
        h_max = max(a.h_max,b.h_max);
        h_min = min(a.h_min,b.h_min);
        w_max = max(a.w_max,b.w_max);
        w_min = min(a.w_min,b.w_min);
    }
    int get_size() {
        if(ures) return 0;
        return (h_max - h_min + 1) * (w_max - w_min + 1);
    }
};

Elem fa[maxn*8];

void epit(int hol, int tol, int ig, vector<int> &R, vector<int> &C) {
    if(tol == ig) {
        fa[hol] = Elem(R[tol],C[tol]);
        return;
    }
    int mid = (tol + ig) / 2;
    epit(hol*2,tol,mid,R,C);
    epit(hol*2+1,mid+1,ig,R,C);
    fa[hol].rep(fa[hol*2],fa[hol*2+1]);
    return;
}

Elem ask(int hol, int tol, int ig, int to) {
    if(ig <= to) {
        return fa[hol];
    }
    Elem uj;
    if(to < tol) {
        return uj;
    }
    int mid = (tol + ig) / 2;
    uj.rep(ask(hol*2,tol,mid,to),ask(hol*2+1,mid+1,ig,to));
    return uj;
}

void modif(int hol, int tol, int ig, int poz, Elem &val) {
    if(tol == ig) {
        fa[hol] = val;
        return;
    }
    int mid = (tol + ig) / 2;
    if(poz <= mid) {
        modif(hol*2,tol,mid,poz,val);
    }
    else {
        modif(hol*2+1,mid+1,ig,poz,val);
    }
    fa[hol].rep(fa[hol*2],fa[hol*2+1]);
    return;
}

int szep = 0;

vector<int> R, C;
int N;

void give_initial_chart(int H, int W, vector<int> RR, vector<int> CC) {
    R = RR;
    C = CC;
    N = H * W;
    epit(1,0,N-1,R,C);
    for(int i=0;i<N;i++) {
        if(ask(1,0,N-1,i).get_size() == i+1) {
            szep++;
            jo[i] = 1;
        }
    }
    return;
}

int swap_seats(int a, int b) {
    swap(R[a],R[b]);
    swap(C[a],C[b]);
    Elem A(R[a],C[a]);
    Elem B(R[b],C[b]);
    modif(1,0,N-1,a,A);
    modif(1,0,N-1,b,B);
    Elem r = ask(1,0,N-1,min(a,b));
    for(int i=min(a,b);i<max(a,b);i++) {
        szep -= jo[i];
        jo[i] = 0;
        if(r.get_size() == i+1) {
            jo[i] = 1;
        }
        szep += jo[i];
        Elem U(R[i+1],C[i+1]);
        r.rep(r,U);
    }
    return szep;
}

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