Submission #284653

#	Time	Username	Problem	Language	Result	Execution time	Memory
284653		peti1234	자리 배치 (IOI18_seats)	C++17	11 / 100	599 ms	140384 KiB

seats

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

const int c=1000002, p=1048576;
vector<vector<int> > pos;
int n, m, k, sor[c], lp[c], oszlop[c], kezd[2*p], veg[2*p], kert[2*p], kdb[2*p], t[4];
bool jo[c];
void add(int a, int st, int fi, int ert) {
    int k=kezd[a], v=veg[a], x=2*a, y=2*a+1;
    //if (a==1) cout << "add " << a << " " << st << " " << fi << " " << ert << " " << k << " " << v << "\n";
    if (st>v || fi<k) return;
    if (st<=k && v<=fi) lp[a]+=ert;
    else {
        add(x, st, fi, ert), add(y, st, fi, ert);
        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][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);
    //cout << a << " " << b << " " << t[0] << " " << t[1] << " " << t[2] << " " << t[3] << endl;
    if (t[0]!=t[1]) add(1, t[0], t[1]-1, c);
    if (t[2]!=t[3]) add(1, t[2], t[3]-1, c);
}
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]][oszlop[a]]=a, pos[sor[b]][oszlop[b]]=b;
    kupd(sor[a], oszlop[a], 1), kupd(sor[b], oszlop[b], 1);
    /*for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) cout << pos[i][j] << " ";
        cout << endl;
    }*/
    return kdb[1];
}
void give_initial_chart(int a, int b, vector<int> c, vector<int> d) {
    n=a, m=b, k=n*m;
    pos.resize(n);
    for (int i=0; i<n; i++) for (int j=0; j<m; j++) pos[i].push_back(0);
    for (int i=0; i<k; i++) sor[i]=c[i], oszlop[i]=d[i], pos[sor[i]][oszlop[i]]=i;
    /*for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) cout << pos[i][j] << " ";
        cout << endl;
    }*/
    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);
    /*for (int i=1; i<2*p; i++) {
        //cout << i << " " << kert[i]+lp[i] << " " << kdb[i] << " " << lp[i] << "\n";
    }*/
}

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