Submission #294455

#	Time	Username	Problem	Language	Result	Execution time	Memory
294455		amiratou	Seats (IOI18_seats)	C++14	17 / 100	4054 ms	43640 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)(x.size())
const int MX = (int)(1e6+3);
const int INF = (int)(1e9);
typedef pair<int,int> ii;

int ans[MX],fen[MX];
vector<int> r,c;
ii range[MX][2];
void update(int idx,int val){
	for (int i = idx; i <= sz(r); i+=(i&(-i)))
		fen[i]+=val;
}
int get(int idx){
	int h=0;
	for (int i = idx; i >= 1; i-=(i&(-i)))
		h+=fen[i];
	return h;
}
void add(int a,int b,int val){
	update(a,val);
	if(b!=sz(r))update(b+1,-val);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	r=R,c=C;
	for (int i = 0; i < H*W; ++i)
	{
		range[i][0]=range[i][1]={INF,-1};
		if(i){
			range[i][0].fi=min(range[i][0].fi,range[i-1][0].fi);
			range[i][0].se=max(range[i][0].se,range[i-1][0].se);
			range[i][1].fi=min(range[i][1].fi,range[i-1][1].fi);
			range[i][1].se=max(range[i][1].se,range[i-1][1].se);
			int k=get(i);
			add(i+1,i+1,k);
		}
		range[i][0].fi=min(range[i][0].fi,R[i]);
		range[i][0].se=max(range[i][0].se,R[i]);
		range[i][1].fi=min(range[i][1].fi,C[i]);
		range[i][1].se=max(range[i][1].se,C[i]);
		if(((range[i][0].se-range[i][0].fi+1)*(range[i][1].se-range[i][1].fi+1))==(i+1))add(i+1,i+1,1);
	}
}

int swap_seats(int a, int b) {
	if(a>b)swap(a,b);
	swap(r[a],r[b]),swap(c[a],c[b]);
	if(b!=sz(r)){
		int k=get(b+1);
		add(b+2,sz(r),-k);
	}
	for (int i = a; i <= b; ++i)
	{
		range[i][0]=range[i][1]={INF,-1};
		int k=get(i+1);
		add(i+1,i+1,-k);
		if(i){
			range[i][0].fi=min(range[i][0].fi,range[i-1][0].fi);
			range[i][0].se=max(range[i][0].se,range[i-1][0].se);
			range[i][1].fi=min(range[i][1].fi,range[i-1][1].fi);
			range[i][1].se=max(range[i][1].se,range[i-1][1].se);
			int k=get(i);
			add(i+1,i+1,k);
		}
		range[i][0].fi=min(range[i][0].fi,r[i]);
		range[i][0].se=max(range[i][0].se,r[i]);
		range[i][1].fi=min(range[i][1].fi,c[i]);
		range[i][1].se=max(range[i][1].se,c[i]);
		if(((range[i][0].se-range[i][0].fi+1)*(range[i][1].se-range[i][1].fi+1))==(i+1))add(i+1,i+1,1);
	}
	if(b!=sz(r)){
		int k=get(b+1);
		add(b+2,sz(r),k);
	}
	return get(sz(r));
}

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