Submission #156702

#	Time	Username	Problem	Language	Result	Execution time	Memory
156702		wilwxk	Seats (IOI18_seats)	C++14	0 / 100	4085 ms	108288 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e6+3;
vector<vector<int> > matriz;
pair<int, int> wh[MAXN];
vector<vector<int> > seg;
int sg[MAXN*4][4];
int n, m, respf;

void remerge2(int sind, int e, int d) {
	seg[sind].resize(seg[e].size());
	for(int i=0; i<seg[sind].size(); i++) seg[sind][i]=max(seg[e][i], seg[d][i]);
}
void buildm(int sind, int ini, int fim, int k, int linha) {
	if(ini==fim) {
		seg[k][sind]=matriz[linha][ini];
		return;
	}
	int e=sind*2; int d=e+1;
	int mid=(ini+fim)>>1;
	buildm(e, ini, mid, k, linha);
	buildm(d, mid+1, fim, k, linha);
	seg[k][sind]=max(seg[k][e], seg[k][d]);
}
void buildn(int sind, int ini, int fim) {
	if(ini==fim) {
		seg[sind].resize(m*4+3);
		buildm(1, 0, m-1, sind, ini);
		return;
	}
	int e=sind*2; int d=e+1;
	int mid=(ini+fim)>>1;
	buildn(e, ini, mid);
	buildn(d, mid+1, fim);
	remerge2(sind, e, d);
}
void updatem(int sind, int ini, int fim, int i, int j, int k) {
	if(ini==fim) {
		seg[k][sind]=matriz[i][j];
		return;
	}
	int e=sind*2; int d=e+1;
	int mid=(ini+fim)>>1;
	if(j<=mid) updatem(e, ini, mid, i, j, k);
	else updatem(d, mid+1, fim, i, j, k);
	seg[k][sind]=max(seg[k][e], seg[k][d]);
}
void updaten(int sind, int ini, int fim, int i, int j) {
	if(ini==fim) {
		updatem(1, 0, m-1, i, j, sind);
		return;
	}
	int e=sind*2; int d=e+1;
	int mid=(ini+fim)>>1;
	if(i<=mid) updaten(e, ini, mid, i, j);
	else updaten(d, mid+1, fim, i, j);
	remerge2(sind, e, d);
}
int querym(int sind, int ini, int fim, int qini, int qfim, int k) {
	if(qfim<ini||qini>fim) return 0;
	if(qini<=ini&&qfim>=fim) return seg[k][sind];
	int e=sind*2; int d=e+1;
	int mid=(ini+fim)>>1;
	return max(querym(e, ini, mid, qini, qfim, k), querym(d, mid+1, fim, qini, qfim, k));
}
int queryn(int sind, int ini, int fim, int nl, int nr, int ml, int mr) {
	if(nr<ini||nl>fim) return 0;
	if(nl<=ini&&nr>=fim) return querym(1, 0, m-1, ml, mr, sind);
	int e=sind*2; int d=e+1;
	int mid=(ini+fim)>>1;
	return max(queryn(e, ini, mid, nl, nr, ml, mr), queryn(d, mid+1, fim, nl, nr, ml, mr));
}

void remerge(int sind, int e, int d) {
	for(int i=0; i<4; i++) {
		if(i&1) sg[sind][i]=max(sg[e][i], sg[d][i]);
		else sg[sind][i]=min(sg[e][i], sg[d][i]);
	}
}
void build(int sind, int ini, int fim) {
	if(ini==fim) {
		sg[sind][0]=sg[sind][1]=wh[ini].first;
		sg[sind][2]=sg[sind][3]=wh[ini].second;
		return;
	}
	int e=sind*2; int d=e+1;
	int mid=(ini+fim)>>1;
	build(e, ini, mid);
	build(d, mid+1, fim);
	remerge(sind, e, d);
}
void update(int sind, int ini, int fim, int qind) {
	if(ini==fim) {
		sg[sind][0]=sg[sind][1]=wh[ini].first;
		sg[sind][2]=sg[sind][3]=wh[ini].second;
		return;
	}
	int e=sind*2; int d=e+1;
	int mid=(ini+fim)>>1;
	if(qind<=mid) update(e, ini, mid, qind);
	else update(d, mid+1, fim, qind);
}
void query(int sind, int ini, int fim, int qind) {
	if(sind==1) {
		sg[0][0]=sg[0][2]=MAXN*2;
		sg[0][1]=sg[0][3]=-1;
	}
	if(qind>=fim) {
		remerge(0, 0, sind);
		return;
	}
	int e=sind*2; int d=e+1;
	int mid=(ini+fim)>>1;
	query(e, ini, mid, qind);
	if(qind>mid) query(d, mid+1, fim, qind);
}


void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n=H; m=W;
	matriz.resize(n); for(int i=0; i<n; i++) matriz[i].resize(m);
	for(int i=0; i<n*m; i++) {
		wh[i]={R[i], C[i]};
		matriz[R[i]][C[i]]=i;
	}
	seg.resize(n*4+3);
	buildn(1, 0, n-1);
	build(1, 0, n*m-1);

	for(int i=0; i<n*m; i++) {
		query(1, 0, n*m-1, i);
		int tam=sg[0][1]-sg[0][0]+1;
		tam*=(sg[0][3]-sg[0][2]+1);
		// printf("%d > %d\n", i, tam);
		if(tam==i+1) respf++;
	}
}

void revert(int a, int b, int k) {
	int tam,  p=a;
	while(p<=b) {
		query(1, 0, n*m-1, p);
		tam=sg[0][1]-sg[0][0]+1;
		tam*=(sg[0][3]-sg[0][2]+1);
		// printf("%d > %d\n", p, tam);
		if(tam-1==p) {
			respf+=k;
			p++;
		}
		else {
			p=queryn(1, 0, n-1, sg[0][0], sg[0][1], sg[0][2], sg[0][3]);
		}
	}
}

int swap_seats(int a, int b) {
	if(a>b) swap(a, b);
	//unmount
	revert(a, b, -1);

	swap(wh[a], wh[b]);
	matriz[wh[a].first][wh[a].second]=a;
	matriz[wh[b].first][wh[b].second]=b;
	update(1, 0, n*m-1, a);
	update(1, 0, n*m-1, b);
	updaten(1, 0, n-1, wh[a].first, wh[a].second);
	updaten(1, 0, n-1, wh[b].first, wh[b].second);

	//mount
	revert(a, b, 1);
	return respf;
}

Compilation message (stderr)

seats.cpp: In function 'void remerge2(int, int, int)':
seats.cpp:14:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<seg[sind].size(); i++) seg[sind][i]=max(seg[e][i], seg[d][i]);
               ~^~~~~~~~~~~~~~~~~

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