Submission #831447

#	Time	Username	Problem	Language	Result	Execution time	Memory
831447		tolbi	Seats (IOI18_seats)	C++17	0 / 100	4061 ms	47804 KiB

seats

#include <bits/stdc++.h>
using namespace std;
#include "seats.h"
#define tol(bi) (1LL<<((int)(bi)))
struct BIT{
	vector<int> arr;
	BIT(int n){
		arr.resize(n,0);
	}
	void update(int x, int val){
		arr[x]=val;
	}
	int query(int l, int r){
		int rval = 0;
		for (int i = l; i <= r; i++){
			rval=max(rval,arr[i]);
		}
		return rval;
	}
};
vector<int> R,C;
vector<BIT> horizontal;
vector<BIT> vertical;
void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
	R=_R,C=_C;
	horizontal.resize(W,H);
	vertical.resize(H,W);
	for (int i = 0; i < R.size(); ++i)
	{
		vertical[R[i]].update(C[i],i);
		horizontal[C[i]].update(R[i],i);
	}
}

int swap_seats(int a, int b) {
	swap(R[a],R[b]);
	swap(C[a],C[b]);
	vertical[R[a]].update(C[a],a);
	vertical[R[b]].update(C[b],b);
	horizontal[C[a]].update(R[a],a);
	horizontal[C[b]].update(R[b],b);
	int n = R.size();
	int crmax = 0;
	int ans = 1;
	int xl=R[0],xr=R[0];
	int yl=C[0],yr=C[0];
	while (crmax<R.size()-1){
		int sec1=n, sec2=n, sec3=n, sec4=n;
		if (yl>0){
			sec1=horizontal[yl-1].query(xl,xr);
		}
		if (yr<horizontal.size()-1){
			sec2=horizontal[yr+1].query(xl,xr);
		}
		if (xl>0){
			sec3=vertical[xl-1].query(yl,yr);
		}
		if (xr<vertical.size()-1){
			sec4=vertical[xr+1].query(yl,yr);
		}
		int minel = n;
		minel=min(minel,sec1);
		minel=min(minel,sec2);
		minel=min(minel,sec3);
		minel=min(minel,sec4);
		xr=max(xr,R[minel]);
		xl=min(xl,R[minel]);
		yr=max(yr,C[minel]);
		yl=min(yl,C[minel]);
		crmax=max(crmax,minel);
		if ((xr-xl+1)*(yr-yl+1)==crmax+1) ans++;
	}
	return ans;
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 0; i < R.size(); ++i)
      |                  ~~^~~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:47:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  while (crmax<R.size()-1){
      |         ~~~~~^~~~~~~~~~~
seats.cpp:52:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<BIT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   if (yr<horizontal.size()-1){
      |       ~~^~~~~~~~~~~~~~~~~~~~
seats.cpp:58:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<BIT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   if (xr<vertical.size()-1){
      |       ~~^~~~~~~~~~~~~~~~~~

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