Submission #1049552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049552		SiliconSquared	Seats (IOI18_seats)	C++14	17 / 100	4053 ms	56660 KiB

seats

#include "seats.h"
#define INF 999999999
using namespace std;
#include <vector>
#include <cmath>

int h,w,zz;
vector<int> x;
vector<int> x_;
vector<int> y;
vector<int> y_;
vector<bool> z;
vector<int> r;
vector<int> c;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    h=H;
    w=W;
    r=R;
    c=C;
    zz=1;
    x.resize(h*w);
    x_.resize(h*w);
    y.resize(h*w);
    y_.resize(h*w);
    z.resize(h*w,0);
    x[0]=C[0];
    x_[0]=C[0];
    y[0]=R[0];
    y_[0]=R[0];
    z[0]=1;
    for (int i=1;i<h*w;i++){
        x[i]=min(x[i-1],C[i]);//print(x[i]);
        x_[i]=max(x_[i-1],C[i]);//print(x_[i]);
        y[i]=min(y[i-1],R[i]);//print(y[i]);
        y_[i]=max(y_[i-1],R[i]);//print(y_[i]);
        if ((x_[i]+1-x[i])*(y_[i]+1-y[i])==i+1){
            zz++;
            z[i]=1;
        }
    }
}

int swap_seats(int a, int b) {
    if (a>b){swap(a,b);}
    swap(r[a],r[b]);
    swap(c[a],c[b]);
    if (a==0){
        x[0]=c[0];
        x_[0]=c[0];
        y[0]=r[0];
        y_[0]=r[0];
    }
    for (int i=max(a,1);i<b;i++){
        x[i]=min(x[i-1],c[i]);
        x_[i]=max(x_[i-1],c[i]);
        y[i]=min(y[i-1],r[i]);
        y_[i]=max(y_[i-1],r[i]);
        if ((x_[i]+1-x[i])*(y_[i]+1-y[i])==i+1){
            if (z[i]==0){
                zz++;
                z[i]=1;
            }
        }else if (z[i]==1){
            zz--;
            z[i]=0;
        }
    }
    return zz;
}

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