Submission #138263

#	Time	Username	Problem	Language	Result	Execution time	Memory
138263		wilwxk	Seats (IOI18_seats)	C++14	17 / 100	4091 ms	45688 KiB

seats

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

const int MAXN=1e6+5;
vector<int> r, c;
int rmn[MAXN], rmx[MAXN];
int cmn[MAXN], cmx[MAXN];
int resp[MAXN];
int respf;
int n, m;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  n=H; m=W; 
  r=R; c=C;
  int mn=MAXN, mx=-1;
  int mn2=MAXN, mx2=-1;
  for(int i=0; i<n*m; i++) {
  	mn=min(mn, r[i]); mx=max(mx, r[i]);
  	mn2=min(mn2, c[i]); mx2=max(mx2, c[i]);
  	rmn[i]=mn; rmx[i]=mx;
  	cmn[i]=mn2; cmx[i]=mx2;
  	int tam=mx-mn+1; tam*=(mx2-mn2+1);
  	if(i+1==tam) resp[i]=1, respf++;
  	// printf("%d >> %d\n", i, tam);
  } 
  // printf("%d\n", respf);
}

int swap_seats(int a, int b) {
	if(a>b) swap(a, b);
	for(int i=a; i<=b; i++) {
		int tam=rmx[i]-rmn[i]+1; tam*=(cmx[i]-cmn[i]+1);
  		if(i+1==tam) respf--;
	}
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	int mn= a==0 ? MAXN : rmn[a-1];
	int mx= a==0 ? -1 : rmx[a-1];
	int mn2= a==0 ? MAXN : cmn[a-1];
	int mx2= a==0 ? -1 : cmx[a-1];
	for(int i=a; i<=b; i++) {
		mn=min(mn, r[i]); mx=max(mx, r[i]);
		mn2=min(mn2, c[i]); mx2=max(mx2, c[i]);
		rmn[i]=mn; rmx[i]=mx;
		cmn[i]=mn2; cmx[i]=mx2;
		int tam=rmx[i]-rmn[i]+1; tam*=(cmx[i]-cmn[i]+1);
		// printf("%d >> %d\n", i, tam);
  		if(i+1==tam) respf++;
	}
	return respf;
}

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