Submission #132110

#	Time	Username	Problem	Language	Result	Execution time	Memory
132110		dvdg6566	Seats (IOI18_seats)	C++14	17 / 100	4086 ms	55552 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
#define mp make_pair
#define f first
#define s second
#define MAXN 1000000

int ans;
pi L[MAXN];
pi U[MAXN];
int R[MAXN];
int C[MAXN];

void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
  L[0] = U[0] = mp(_R[0],_C[0]);
  R[0]=_R[0];C[0]=_C[0];
  for (int i=1;i<H*W;++i){
  	R[i] = _R[i];C[i]=_C[i];
  	L[i].f= min(L[i-1].f,R[i]);
  	L[i].s= min(L[i-1].s,C[i]);
  	U[i].f= max(U[i-1].f,R[i]);
  	U[i].s= max(U[i-1].s,C[i]);
  }
  for (int i=0;i<H*W;++i){
  	int a = (U[i].s-L[i].s+1) * (U[i].f-L[i].f+1);
  	// cout<<a<<'\n';
  	if (a == i+1){
  		++ans;
  	}
  }
}

int swap_seats(int a, int b) {
  if (a>b)swap(a,b);	
  swap(R[a],R[b]);swap(C[a],C[b]);
  // cout<<R[a]<<' '<<C[a]<<'\n';
  for (int i=a;i<=b;++i){
  	int v = (U[i].s-L[i].s+1) * (U[i].f-L[i].f+1);
  	if (v == i+1){
  		--ans;
  		// cout<<"Sub\n";
  	}
  	if (i == 0){
  		L[i] = U[i] = 	mp(R[i],C[i]);
  		// cout<<R[i]<<' '<<C[i]<<'\n';
  	}else{
  		L[i].f= min(L[i-1].f,R[i]);
  		L[i].s= min(L[i-1].s,C[i]);
  		U[i].f= max(U[i-1].f,R[i]);
  		U[i].s= max(U[i-1].s,C[i]);
  	}
  	v = (U[i].s-L[i].s+1) * (U[i].f-L[i].f+1);
  	// cout<<v<<'\n';
  	if (v == i+1){
  		++ans;
  	}
  }
  // }cout<<'\n';
  return ans;
}

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