Submission #119727

#	Time	Username	Problem	Language	Result	Execution time	Memory
119727		imyujin	Seats (IOI18_seats)	C++14	100 / 100	3592 ms	65912 KiB

seats

#include "seats.h"
#include<vector>
#include<algorithm>

using namespace std;

#define MAXN 1000010

int N, H, W;
vector<int> R, C;
int a[3*MAXN];
int seg[MAXN*6], lazy[MAXN*6], num[MAXN*6];
int t[4];

void mkseg(int idx, int l, int r){
	num[idx]=r-l+1;
	if(l<r){
		int m=l+r>>1;
		mkseg(idx*2, l, m);
		mkseg(idx*2+1, m+1, r);
	}
}

void updseg(int idx, int l, int r, int x, int y, int z){
	//if(idx==1) printf("(%d %d %d)\n", x, y, z);
	if(x<=l&&r<=y){
		lazy[idx]+=z;
		seg[idx]+=z;
	}
	else if(l<=y&&x<=r){
		int m=l+r>>1;
		lazy[idx*2]+=lazy[idx];
		lazy[idx*2+1]+=lazy[idx];
		seg[idx*2]+=lazy[idx];
		seg[idx*2+1]+=lazy[idx];
		lazy[idx]=0;
		updseg(idx*2, l, m, x, y, z);
		updseg(idx*2+1, m+1, r, x, y, z);
		if(seg[idx*2]<seg[idx*2+1]){
			seg[idx]=seg[idx*2];
			num[idx]=num[idx*2];
		}
		else if(seg[idx*2+1]<seg[idx*2]){
			seg[idx]=seg[idx*2+1];
			num[idx]=num[idx*2+1];
		}
		else{
			seg[idx]=seg[idx*2];
			num[idx]=num[idx*2]+num[idx*2+1];
		}
	}
}

void updcor(int i, int j, int z){
	t[0]=a[i*(W+2)+j];
	t[1]=a[i*(W+2)+j+1];
	t[2]=a[(i+1)*(W+2)+j];
	t[3]=a[(i+1)*(W+2)+j+1];
	sort(t, t+4);
	if(t[0]<t[1]) updseg(1, 0, N-1, t[0], t[1]-1, z);
	if(t[2]<t[3]) updseg(1, 0, N-1, t[2], t[3]-1, z);
}

void updsea(int i, int j, int z){
	//printf("{%d %d %d}\n", i, j, z);
	updcor(i, j, z);
	updcor(i, j+1, z);
	updcor(i+1, j, z);
	updcor(i+1, j+1, z);
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
	H=h;
	W=w;
	N=H*W;
	R=r;
	C=c;
	for(int i=0; i<N; i++) a[(R[i]+1)*(W+2)+C[i]+1]=i;
	for(int i=0; i<=H+1; i++) a[i*(W+2)]=a[i*(W+2)+W+1]=N;
	for(int i=0; i<=W+1; i++) a[i]=a[(H+1)*(W+2)+i]=N;
	mkseg(1, 0, N-1);
	for(int i=0; i<=H; i++) for(int j=0; j<=W; j++) updcor(i, j, 1);
	//printf("[%d]\n", num[1]);
}

int swap_seats(int x, int y) {
	updsea(R[x], C[x], -1);
	updsea(R[y], C[y], -1);
	swap(a[(R[x]+1)*(W+2)+C[x]+1], a[(R[y]+1)*(W+2)+C[y]+1]);
	swap(R[x], R[y]);
	swap(C[x], C[y]);
	updsea(R[x], C[x], 1);
	updsea(R[y], C[y], 1);
	return num[1];
}

Compilation message (stderr)

seats.cpp: In function 'void mkseg(int, int, int)':
seats.cpp:18:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=l+r>>1;
         ~^~
seats.cpp: In function 'void updseg(int, int, int, int, int, int)':
seats.cpp:31:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=l+r>>1;
         ~^~

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