Submission #373600

#	Time	Username	Problem	Language	Result	Execution time	Memory
373600		BartolM	Seats (IOI18_seats)	C++17	17 / 100	4100 ms	55604 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1e6+5;

int n, r, c;
int sol=0;
pii p[N], maxi[N], mini[N];

int ok(int i) {
    return (maxi[i].X-mini[i].X+1)*(maxi[i].Y-mini[i].Y+1)==i+1;
}

void upd(int i) {
    maxi[i].X=mini[i].X=p[i].X;
    maxi[i].Y=mini[i].Y=p[i].Y;
    if (i) maxi[i].X=max(maxi[i-1].X, p[i].X), maxi[i].Y=max(maxi[i-1].Y, p[i].Y);
    if (i) mini[i].X=min(mini[i-1].X, p[i].X), mini[i].Y=min(mini[i-1].Y, p[i].Y);
    if (ok(i)) sol++;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n=H*W; r=H; c=W;
    for (int i=0; i<n; ++i) {
        p[i]=mp(R[i], C[i]);
        upd(i);
    }
}

int swap_seats(int a, int b) {
    if (a>b) swap(a, b);
    for (int i=a; i<b; ++i) if (ok(i)) sol--;
    swap(p[a], p[b]);
    for (int i=a; i<b; ++i) upd(i);
    return sol;
}

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