Submission #423606

#	Time	Username	Problem	Language	Result	Execution time	Memory
423606		Pbezz	Seats (IOI18_seats)	C++14	17 / 100	4062 ms	55596 KiB

seats

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

using namespace std;

#define ll int
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 1e6+5;
const ll INF = 1e9+7;

vector<pii>lim1(MAXN);
vector<pii>lim2(MAXN);
bitset<1000004>ok;

std::vector<int> r;
std::vector<int> c;
ll h,w;

void give_initial_chart(int H, int W,std::vector<int> R,std::vector<int> C){
  r = R;
  c = C;
	h=H;
	w=W;

	ll k,area;

	for(k=0;k<H*W;k++){

	if(k==0){
	lim1[0]={R[0],R[0]};
	lim2[0]={C[0],C[0]};
	}else{
	//update

	lim1[k].first=min(lim1[k-1].first,R[k]);
	lim1[k].second=max(lim1[k-1].second,R[k]);

	lim2[k].first=min(lim2[k-1].first,C[k]);
	lim2[k].second=max(lim2[k-1].second,C[k]);

	}
	//area

	area = lim1[k].second-lim1[k].first+1;

	area*=(lim2[k].second-lim2[k].first+1);

	ok[k]=0;
	if(area==k+1){
	ok[k]=1;
	}

	}


}

int swap_seats(int a, int b) {
	swap(r[a],r[b]);
	swap(c[a],c[b]);
	ll k,area;
	if(a>b)swap(a,b);
	for(k=a;k<=b;k++){

	if(k==0){
	lim1[0]={r[0],r[0]};
	lim2[0]={c[0],c[0]};
	}else{
	//update

	lim1[k].first=min(lim1[k-1].first,r[k]);
	lim1[k].second=max(lim1[k-1].second,r[k]);

	lim2[k].first=min(lim2[k-1].first,c[k]);
	lim2[k].second=max(lim2[k-1].second,c[k]);

	}
	//area

	area = lim1[k].second-lim1[k].first+1;

	area*=(lim2[k].second-lim2[k].first+1);

	ok[k]=0;
	if(area==k+1){
	ok[k]=1;
	}

	}





  return ok.count();
}

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