Submission #758310

#	Time	Username	Problem	Language	Result	Execution time	Memory
758310		alexander707070	Seats (IOI18_seats)	C++14	11 / 100	4091 ms	39744 KiB

seats

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

int n,m,minx[MAXN],miny[MAXN],maxx[MAXN],maxy[MAXN],ans;
pair<int,int> w[MAXN];

int swap_seats(int x,int y){
    x++; y++;

    for(int i=1;i<=n*m;i++){
        minx[i]=minx[i-1];
        maxx[i]=maxx[i-1];
        miny[i]=miny[i-1];
        maxy[i]=maxy[i-1];

        minx[i]=min(minx[i],w[i].first);
        maxx[i]=max(maxx[i],w[i].first);
        miny[i]=min(miny[i],w[i].second);
        maxy[i]=max(maxy[i],w[i].second);

        if((maxx[i]-minx[i]+1)*(maxy[i]-miny[i]+1)==i)ans--;
    }

    swap(w[x],w[y]);

    for(int i=1;i<=n*m;i++){
        minx[i]=minx[i-1];
        maxx[i]=maxx[i-1];
        miny[i]=miny[i-1];
        maxy[i]=maxy[i-1];

        minx[i]=min(minx[i],w[i].first);
        maxx[i]=max(maxx[i],w[i].first);
        miny[i]=min(miny[i],w[i].second);
        maxy[i]=max(maxy[i],w[i].second);

        if((maxx[i]-minx[i]+1)*(maxy[i]-miny[i]+1)==i)ans++;
    }

    return ans;
}

void give_initial_chart(int H, int W,vector<int> R,vector<int> C){
    n=H; m=W;
    for(int i=1;i<=n*m;i++){
        w[i]={R[i-1],C[i-1]};
    }
    minx[0]=miny[0]=n+m;
    maxx[0]=maxy[0]=-1;

    for(int i=1;i<=n*m;i++){
        minx[i]=minx[i-1];
        maxx[i]=maxx[i-1];
        miny[i]=miny[i-1];
        maxy[i]=maxy[i-1];

        minx[i]=min(minx[i],w[i].first);
        maxx[i]=max(maxx[i],w[i].first);
        miny[i]=min(miny[i],w[i].second);
        maxy[i]=max(maxy[i],w[i].second);

        if((maxx[i]-minx[i]+1)*(maxy[i]-miny[i]+1)==i)ans++;
    }
}

/*
int main(){

    give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1,1, 2, 2});
    cout<<swap_seats(0, 5)<<" "<<swap_seats(0, 5)<<"\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