Submission #81165

#	Time	Username	Problem	Language	Result	Execution time	Memory
81165		cki86201	Seats (IOI18_seats)	C++11	20 / 100	2758 ms	221732 KiB

seats

#include "seats.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int R[1000010], C[1000010];
int valR[1000010][2], valC[1000010][2];
int N, M, P;
int ans;

int subtask_3;
namespace S3 {
    set <int> sx[1010], sy[1010];
    int solve(int N, int M) {
        vector <pii> A(N+1), B(M+1);
        for(int i=1;i<=N+1;i++) A[i-1] = pii(*sx[i].begin(), i);
        for(int i=1;i<=M+1;i++) B[i-1] = pii(*sy[i].begin(), i);
        sort(all(A)); sort(all(B));
        int valr[2] = {A[0].Se, A[0].Se};
        int valc[2] = {B[0].Se, B[0].Se};
        int res = 0;
        for(int i=1, j=1;i<=N;i++) {
            while(j <= M && B[j].Fi < A[i].Fi) {
                if((valr[1]-valr[0]+1) * (valc[1]-valc[0]+1) == B[j].Fi-1) ++res;
                valc[1] = max(valc[1], B[j].Se);
                valc[0] = min(valc[0], B[j].Se);
                ++j;
            }
            if((valr[1]-valr[0]+1) * (valc[1]-valc[0]+1) == A[i].Fi-1) ++res;
            valr[1] = max(valr[1], A[i].Se);
            valr[0] = min(valr[0], A[i].Se);
        }
        return res;
    }
}

int check_on_naive(int x) {
    return (valR[x][1] - valR[x][0] + 1) * (valC[x][1] - valC[x][0] + 1) == x;
}

void give_initial_chart(int H, int W, std::vector<int> tR, std::vector<int> tC) {
    N = H; M = W;
    P = N * M;
    rep(i, P) R[i + 1] = tR[i] + 1, C[i + 1] = tC[i] + 1;
    
    
    if(H <= 1000 && W <= 1000) {
        subtask_3 = 1;
        for(int i=1;i<=P;i++) {
            S3::sx[R[i]].insert(i);
            S3::sy[C[i]].insert(i);
        }
        S3::sx[H+1].insert(P+1);
        S3::sy[W+1].insert(P+1);
        return;
    }
    
    valR[0][0] = 1e9, valR[0][1] = -1;
    valC[0][0] = 1e9, valC[0][1] = -1;
    for(int i=1;i<=P;i++) {
        valR[i][0] = min(valR[i-1][0], R[i]);
        valR[i][1] = max(valR[i-1][1], R[i]);
        valC[i][0] = min(valC[i-1][0], C[i]);
        valC[i][1] = max(valC[i-1][1], C[i]);
    }
    for(int i=1;i<=P;i++) {
        ans += check_on_naive(i);
    }
}

int swap_seats(int a, int b) {
    ++a; ++b;
    if(subtask_3) {
        int ra = R[a], rb = R[b];
        S3::sx[ra].erase(a); S3::sx[ra].insert(b);
        S3::sx[rb].erase(b); S3::sx[rb].insert(a);
        int ca = C[a], cb = C[b];
        S3::sy[ca].erase(a); S3::sy[ca].insert(b);
        S3::sy[cb].erase(b); S3::sy[cb].insert(a);
        swap(R[a], R[b]);
        swap(C[a], C[b]);
        return S3::solve(N, M);
    }
    
    if(b-a <= 10000) {
        swap(R[a], R[b]);
        swap(C[a], C[b]);
        for(int i=a;i<b;i++) ans -= check_on_naive(i);
        for(int i=a;i<b;i++) {
            valR[i][0] = min(valR[i-1][0], R[i]);
            valR[i][1] = max(valR[i-1][1], R[i]);
            valC[i][0] = min(valC[i-1][0], C[i]);
            valC[i][1] = max(valC[i-1][1], C[i]);
            ans += check_on_naive(i);
        }
        return ans;
    }
    return 0;
}

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