Submission #1038557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038557		vjudge1	Seats (IOI18_seats)	C++17	17 / 100	4038 ms	58060 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
int ans;
vector<int>R_,C_,R2,C2,R3,C3;
int span(int pos){
    return (R3[pos]-R2[pos]+1)*(C3[pos]-C2[pos]+1);
}
void red(int i){
    R2[i]=min(R2[i-1],R_[i]);
    R3[i]=max(R3[i-1],R_[i]);
    C2[i]=min(C2[i-1],C_[i]);
    C3[i]=max(C3[i-1],C_[i]);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    R_=R,C_=C;
    R_.insert(R_.begin(),0);
    C_.insert(C_.begin(),0);
    R2=R3=C2=C3=R_;
    R2[0]=C2[0]=1e9;
    for(int i=0;i<H*W;)
        red(++i),ans+=i==span(i);
}

int swap_seats(int a, int b) {
    a++,b++;
    if(a>b)swap(a,b);
    swap(R_[a],R_[b]);
    swap(C_[a],C_[b]);
    for(int i=a;i<b;i++)
        ans-=i==span(i),red(i),ans+=i==span(i);
    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