Submission #599902

#	Time	Username	Problem	Language	Result	Execution time	Memory
599902		Hanksburger	Seats (IOI18_seats)	C++17	17 / 100	4101 ms	40472 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> x, y, xmn, ymn, xmx, ymx;
int n, m, sum;
void give_initial_chart(int N, int M, vector<int> X, vector<int> Y)
{
    n=N;
    m=M;
    x=X;
    y=Y;
    for (int i=0; i<n*m; i++)
    {
        if (!i)
        {
            xmn.push_back(x[i]);
            ymn.push_back(y[i]);
            xmx.push_back(x[i]);
            ymx.push_back(y[i]);
        }
        else
        {
            xmn.push_back(min(xmn[i-1], x[i]));
            ymn.push_back(min(ymn[i-1], y[i]));
            xmx.push_back(max(xmx[i-1], x[i]));
            ymx.push_back(max(ymx[i-1], y[i]));
        }
        sum+=((xmx[i]-xmn[i]+1)*(ymx[i]-ymn[i]+1)==i+1);
    }
}
int swap_seats(int a, int b)
{
    if (a>b)
        swap(a, b);
    for (int i=a; i<b; i++)
        sum-=((xmx[i]-xmn[i]+1)*(ymx[i]-ymn[i]+1)==i+1);
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    for (int i=a; i<b; i++)
    {
        if (!i)
        {
            xmn[i]=x[i];
            ymn[i]=y[i];
            xmx[i]=x[i];
            ymx[i]=y[i];
        }
        else
        {
            xmn[i]=min(xmn[i-1], x[i]);
            ymn[i]=min(ymn[i-1], y[i]);
            xmx[i]=max(xmx[i-1], x[i]);
            ymx[i]=max(ymx[i-1], y[i]);
        }
        sum+=((xmx[i]-xmn[i]+1)*(ymx[i]-ymn[i]+1)==i+1);
    }
    return sum;
}

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