Submission #492209

#	Time	Username	Problem	Language	Result	Execution time	Memory
492209		peti1234	Seats (IOI18_seats)	C++17	70 / 100	4059 ms	85444 KiB

seats

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

const int c=1000002, p=1048576;
int n, m, k, s[c], pos[c], o[c], f[2*p], g[2*p], e[2*p], w[2*p], lp[2*p], t[4];
bool jo[c];
int ert;
void add(int a, int st, int fi) {
    int k=f[a], v=g[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, st, fi), add(y, st, fi);
        int p=e[x]+lp[x], q=e[y]+lp[y];
        e[a]=min(p, q);
        w[a]=0;
        if (e[a]==p) w[a]+=w[x];
        if (e[a]==q) w[a]+=w[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]) add(1, t[0], t[1]-1);
    if (t[2]!=t[3]) add(1, t[2], t[3]-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(s[a], o[a], -1), kupd(s[b], o[b], -1);
    swap(s[a], s[b]), swap(o[a], o[b]);
    pos[s[a]*m+o[a]]=a, pos[s[b]*m+o[b]]=b;
    kupd(s[a], o[a], 1), kupd(s[b], o[b], 1);
    return w[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++) s[i]=c[i], o[i]=d[i], pos[s[i]*m+o[i]]=i;
    for (int i=p; i<2*p; i++) {
        int x=i-p;
        f[i]=min(x, k-1), g[i]=min(x, k-1), w[i]=1;
        if (x<k) e[i]=0;
        else e[i]=p;
    }
    for (int i=p-1; i>=0; i--) {
        int x=2*i, y=2*i+1;
        f[i]=f[x], g[i]=g[y];
        e[i]=min(e[x], e[y]);
        if (e[x]==e[i]) w[i]+=w[x];
        if (e[y]==e[i]) w[i]+=w[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: 0 / 30