// moreflags=grader.cpp
// subtask (H==1)
// :(
#include "seats.h"
#include<vector>
#include<climits>
#include<algorithm>
#if LOCAL
#include<iostream>
#else
#define NDEBUG
#endif
#include<cassert>
struct Tree{
struct T{
int minimum, count;
T operator+(int lazy) const{return {minimum+lazy, count};}
T operator+(T other) const{
if(minimum<other.minimum) return *this;
if(minimum>other.minimum) return other;
return {minimum, count+other.count};
}
};
struct Node{
int lazy;
T data_;
T data() const{return data_+lazy;}
};
std::vector<Node> data;
Tree(){}
Tree(int number): data(number*2, {0, {0, 1}}){}
// note: initial state is inconsistent (counts values of nonleafs are 1)
void add(int left, int right, int value){
if(left==right) return;
assert(left<right);
left+=int(data.size()/2); right+=int(data.size()/2);
std::array<int, 2> const old{{left, right-1}};
for(; left<right; left>>=1, right>>=1){
if(left&1) data[left++].lazy+=value;
if(right&1) data[--right].lazy+=value;
}
for(auto it: old){
for(it>>=1; it; it>>=1){
data[it].data_=data[it*2].data()+data[it*2+1].data();
}
}
}
/* // not necessary (...)
void get(int left, int right){
assert(left<right);
left+=int(data.size()/2); right+=int(data.size()/2);
for(auto it: {left, right-1}){
for(int shift=31^__builtin_clz(it); shift; --shift){
auto const node=it>>shift;
if(auto const l=data[node].lazy){
data[node].lazy=0;
data[node].data_.minimum+=l;
data[node*2].lazy+=l;
data[node*2+1].lazy+=l;
}
}
}
T result{};
}
*/
int get(){
// operator+ is commutative
auto const d=data[1].data();
assert(d.minimum>=2);
return d.minimum==2 ? d.count: 0;
}
};
struct MyData{
MyData(){}
//int width;
std::vector<int> value; // pos -> time (in 0..H*W), with two padded (H*W) values on the sides
std::vector<int> R, C; // time -> pos
Tree tree;
MyData(int const H, int const W, std::vector<int> R_, std::vector<int> C_):
//width(W),
value(W+2),
R(std::move(R_)), C(std::move(C_)),
tree(W)
{
if(H!=1)
std::exit(1);
for(int time=0; time<W; ++time){
assert(R[time]==0);
value[C[time]+1]=time;
}
value[0]=value.back()=W;
for(int i=1; i<(int)value.size(); ++i){
auto const [a, b]=std::minmax({value[i-1], value[i]});
tree.add(a, b, 1);
}
}
int swap(int first, int sec){
assert(value[C[first]+1]==first);
assert(value[C[sec]+1]==sec);
assert(R[first]==0); assert(R[sec]==0);
std::swap(C[first], C[sec]);
std::array<int, 4> lefts{{C[first], C[first]+1, C[sec], C[sec]+1}};
std::sort(begin(lefts), end(lefts));
auto const last=std::unique(begin(lefts), end(lefts));
std::for_each(lefts.begin(), last, [&](auto const& it){
auto const [a, b]=std::minmax({value[it], value[it+1]});
tree.add(a, b, -1);
});
value[C[first]+1]=first;
value[C[sec]+1]=sec;
std::for_each(lefts.begin(), last, [&](auto const& it){
auto const [a, b]=std::minmax({value[it], value[it+1]});
tree.add(a, b, 1);
});
return tree.get();
}
} myData;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
myData=MyData{H, W, std::move(R), std::move(C)};
}
int swap_seats(int a, int b) {
return myData.swap(a, b);
}
