Submission #226674

#	Time	Username	Problem	Language	Result	Execution time	Memory
226674		AaronNaidu	Seats (IOI18_seats)	C++14	17 / 100	4086 ms	56616 KiB

seats

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

int h, w;
vector<int> r, c;

bool works[1000001];
int minRow[1000001];
int maxRow[1000001];
int minCol[1000001];
int maxCol[1000001];
int totCount;

void give_initial_chart(int lh, int lw, vector<int> lr, vector<int> lc) {
    h = lh;
    w = lw;
    r = lr;
    c = lc;
    totCount = 1;
    minRow[0] = r[0];
    maxRow[0] = r[0];
    minCol[0] = c[0];
    maxCol[0] = c[0];
    for (int i = 1; i < h * w; i++)
    {
        minRow[i] = min(minRow[i-1], r[i]);
        maxRow[i] = max(maxRow[i-1], r[i]);
        minCol[i] = min(minCol[i-1], c[i]);
        maxCol[i] = max(maxCol[i-1], c[i]);
        if ((maxRow[i] - minRow[i] + 1) * (maxCol[i] - minCol[i] + 1) == i+1)
        {
            //cout << "Rectangle with first " << i+1 << "\n";
            works[i] = true;
            totCount++;
        }
    }
    //cout << "Count initially is " << totCount << "\n";
}

int swap_seats(int a, int b) {
    //cout << "Count now is " << totCount << "\n";
    //cout << "Swapping\n";
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    if (min(a, b) == 0)
    {
        minRow[0] = r[0];
        maxRow[0] = r[0];
        minCol[0] = c[0];
        maxCol[0] = c[0];
    }
    for (int i = max(min(a, b), 1); i <= max(a, b); i++)
    {
        //cout << "i = " << i << "\n";
        minRow[i] = min(minRow[i-1], r[i]);
        maxRow[i] = max(maxRow[i-1], r[i]);
        minCol[i] = min(minCol[i-1], c[i]);
        maxCol[i] = max(maxCol[i-1], c[i]);
        //cout << "Goes from " << minRow[i] << " " << minCol[i] << " to " << maxRow[i] << " " << maxCol[i] << "\n";
        if (works[i])
        {
            totCount--;
            //cout << "Decrease count to " << totCount << "\n";
        }
        if ((maxRow[i] - minRow[i] + 1) * (maxCol[i] - minCol[i] + 1) == i+1)
        {
            //cout << "Rectangle with first " << i+1 << "\n";
            works[i] = true;
            totCount++;
            //cout << "Increase count to " << totCount << "\n";
        }
        else
        {
            works[i] = false;
        }
        
    }
    return totCount;
}

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