Submission #492211

#	Time	Username	Problem	Language	Result	Execution time	Memory
492211		peti1234	Seats (IOI18_seats)	C++17	100 / 100	3342 ms	85424 KiB

seats

#include <bits/stdc++.h>
using namespace std;
 
const int c=1000002, p=1048576;
int n, m, k, sor[c], pos[c], oszlop[c], kezd[2*p], veg[2*p], kert[2*p], kdb[2*p], lp[2*p], t[4];
bool jo[c];
int st, fi, ert;
void add(int a) {
    int k=kezd[a], v=veg[a], x=2*a, y=2*a+1;
    if (st>v || fi<k) return;
    if (st<=k && v<=fi) lp[a]+=ert;
    else {
        add(x), add(y);
        int p=kert[x]+lp[x], q=kert[y]+lp[y];
        kert[a]=min(p, q);
        kdb[a]=0;
        if (kert[a]==p) kdb[a]+=kdb[x];
        if (kert[a]==q) kdb[a]+=kdb[y];
    }
}
int ki(int a, int b) {
    if (a<0 || a>=n || b<0 || b>=m) return k;
    return pos[a*m+b];
}
void upd(int a, int b, int c) {
    t[0]=ki(a-1, b-1), t[1]=ki(a-1, b), t[2]=ki(a, b-1), t[3]=ki(a, b);
    sort(t, t+4);
    ert=c;
    if (t[0]!=t[1]) st=t[0], fi=t[1]-1, add(1);
    if (t[2]!=t[3]) st=t[2], fi=t[3]-1, add(1);
}
void kupd(int a, int b, int c) {
    upd(a+1, b+1, c), upd(a+1, b, c);
    upd(a, b+1, c), upd(a, b, c);
}
int swap_seats(int a, int b) {
    kupd(sor[a], oszlop[a], -1), kupd(sor[b], oszlop[b], -1);
    swap(sor[a], sor[b]), swap(oszlop[a], oszlop[b]);
    pos[sor[a]*m+oszlop[a]]=a, pos[sor[b]*m+oszlop[b]]=b;
    kupd(sor[a], oszlop[a], 1), kupd(sor[b], oszlop[b], 1);
    return kdb[1];
}
void give_initial_chart(int a, int b, vector<int> c, vector<int> d) {
    n=a, m=b, k=n*m;
    for (int i=0; i<k; i++) sor[i]=c[i], oszlop[i]=d[i], pos[sor[i]*m+oszlop[i]]=i;
    for (int i=p; i<2*p; i++) {
        int x=i-p;
        kezd[i]=x, veg[i]=x, kdb[i]=1;
        if (x<k) kert[i]=0;
        else kert[i]=p;
    }
    for (int i=p-1; i>=0; i--) {
        int x=2*i, y=2*i+1;
        kezd[i]=kezd[x], veg[i]=veg[y];
        kert[i]=min(kert[x], kert[y]);
        if (kert[x]==kert[i]) kdb[i]+=kdb[x];
        if (kert[y]==kert[i]) kdb[i]+=kdb[y];
    }
    for (int i=0; i<=n; i++) for (int j=0; j<=m; j++) upd(i, j, 1);
}

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