Submission #342219

#	Time	Username	Problem	Language	Result	Execution time	Memory
342219		Doxeno	Seats (IOI18_seats)	C++17	17 / 100	4061 ms	56940 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
const int MAXN = 1000001;
int x[MAXN], y[MAXN], minx[MAXN],miny[MAXN], maxx[MAXN], maxy[MAXN];
int ans;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    for(int i = 0; i < H*W; i++){
        x[i] = R[i];
        y[i] = C[i];
    }
    maxx[0] = x[0];
    minx[0] = x[0];
    miny[0] = y[0];
    maxy[0] = y[0];
    ans = 1;
    for(int i = 1; i < H*W; i++){
        maxx[i] = max(maxx[i-1],x[i]);
        maxy[i] = max(maxy[i-1],y[i]);
        minx[i] = min(minx[i-1],x[i]);
        miny[i] = min(miny[i-1],y[i]);
        if((ll)(maxy[i]-miny[i]+1)*(maxx[i]-minx[i]+1) == i+1)ans++;
    }
}

int swap_seats(int a, int b) {
    if(a > b)swap(a,b);
    for(int i = a; i <= b; i++){
        if((ll)(maxy[i]-miny[i]+1)*(maxx[i]-minx[i]+1) == i+1)ans--;
    }
    swap(x[a],x[b]);
    swap(y[a],y[b]);
    if(a == 0){
        maxx[0] = x[0];
        minx[0] = x[0];
        miny[0] = y[0];
        maxy[0] = y[0];
        a++; ans++;
    }
    for(int i = a; i <= b; i++){
        maxx[i] = max(maxx[i-1],x[i]);
        maxy[i] = max(maxy[i-1],y[i]);
        minx[i] = min(minx[i-1],x[i]);
        miny[i] = min(miny[i-1],y[i]);
        if((ll)(maxy[i]-miny[i]+1)*(maxx[i]-minx[i]+1) == i+1)ans++;
    }
    return ans;
}

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