제출 #766287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766287		amunduzbaev	자리 배치 (IOI18_seats)	C++17	0 / 100	4083 ms	223816 KiB

seats

#include "seats.h"

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

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll

const int N = 1e6 + 5;
const int inf = 1e9 + 7;

struct ST{
	vector<int> Min, Max;
	int N;
	
	ST(int N): N(N){
		Min.resize(N << 2);
		Max.resize(N << 2);
	}
	
	void set(int i, int v, int lx, int rx, int x){
		if(lx == rx) { Min[x] = Max[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		Min[x] = min(Min[x << 1], Min[x << 1 | 1]);
		Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
	}
	
	void set(int i, int v){
		set(i, v, 0, N, 1);
	}
	
	int getmax(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return Max[x];
		
		int m = (lx + rx) >> 1;
		return max(getmax(l, r, lx, m, x << 1), getmax(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int getmax(int l, int r){
		return getmax(l, r, 0, N, 1);
	}
	
	int getmin(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return inf;
		if(lx >= l && rx <= r) return Min[x];
		
		int m = (lx + rx) >> 1;
		return min(getmin(l, r, lx, m, x << 1), getmin(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int getmin(int l, int r){
		return getmin(l, r, 0, N, 1);
	}
};
//~ }X(N), Y(N);


int cnt, sz, n, m;
bool is;
deque<ar<int, 2>> mnx, mxx, mny, mxy;
vector<int> x, y;
vector<set<int>> X, Y;

//~ bool check(int i){
	//~ if((mxx[i] - mnx[i] + 1) * (mxy[i] - mny[i] + 1) == i + 1){
		//~ return true;
	//~ }
	
	//~ return false;
//~ }

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
	n = h, m = w;
	sz = n * m;
	X.resize(n), Y.resize(m);
	//~ mnx.resize(sz);
	//~ mxx.resize(sz);
	//~ mny.resize(sz);
	//~ mxy.resize(sz);
	swap(x, r);
	swap(y, c);
	
	//~ cnt = 0;
	//~ for(int i=0;i<sz;i++){
		//~ mnx[i] = mxx[i] = x[i];
		//~ mny[i] = mxy[i] = y[i];
		//~ if(i){
			//~ mnx[i] = min(mnx[i], mnx[i - 1]);
			//~ mny[i] = min(mny[i], mny[i - 1]);
			//~ mxx[i] = max(mxx[i], mxx[i - 1]);
			//~ mxy[i] = max(mxy[i], mxy[i - 1]);
		//~ }
		
		//~ if(check(i)) cnt++;
	//~ }
	
	is = 0;
	if(max(n, m) <= 1000){
		is = 1;
		for(int i=0;i<sz;i++){
			X[x[i]].insert(i);
			Y[y[i]].insert(i);
			//~ X.set(i, x[i]);
			//~ Y.set(i, y[i]);
		}
		
		for(int i=n-1;~i;i--){
			int p = *X[i].begin();
			if(mxx.empty() || p < mxx[0][0]) mxx.push_front({p, i});
			while(!mnx.empty() && mnx.back()[1] > p) mnx.pop_back();
			mnx.push_back({p, i});
		}
		
		for(int i=m-1;~i;i--){
			int p = *Y[i].begin();
			if(mxy.empty() || p < mxy[0][0]) mxy.push_front({p, i});
			while(!mny.empty() && mny.back()[1] > p) mny.pop_back();
			mny.push_back({p, i});
		}
	}
}

int ans(int i, int j){
	X[x[i]].erase(i), Y[y[i]].erase(i);
	X[x[j]].erase(j), Y[y[j]].erase(j);
	swap(x[i], x[j]), swap(y[i], y[j]);
	X[x[i]].insert(i), Y[y[i]].insert(i);
	X[x[j]].insert(j), Y[y[j]].insert(j);
	for(int i=n-1;~i;i--){
		int p = *X[i].begin();
		if(mxx.empty() || p < mxx[0][0]) mxx.push_front({p, i});
		while(!mnx.empty() && mnx.back()[1] > p) mnx.pop_back();
		mnx.push_back({p, i});
	}
	
	for(int i=m-1;~i;i--){
		int p = *Y[i].begin();
		if(mxy.empty() || p < mxy[0][0]) mxy.push_front({p, i});
		while(!mny.empty() && mny.back()[1] > p) mny.pop_back();
		mny.push_back({p, i});
	}
	
	int last = 1, res = 1, cnt = 0;
	while(last < sz){
		int mnx_ = (*--lower_bound(mnx.begin(), mnx.end(), (ar<int, 2>){last + 1, 0}))[1];
		int mxx_ = (*--lower_bound(mxx.begin(), mxx.end(), (ar<int, 2>){last + 1, 0}))[1];
		int mny_ = (*--lower_bound(mny.begin(), mny.end(), (ar<int, 2>){last + 1, 0}))[1];
		int mxy_ = (*--lower_bound(mxy.begin(), mxy.end(), (ar<int, 2>){last + 1, 0}))[1];
		int area = (mxx_ - mnx_ + 1) * (mxy_ - mny_ + 1);
		if(area == last + 1){
			last++;
			res++;
		} else {
			last = area - 1;
		}
		cnt++;
	}
	
	return res;
}

int swap_seats(int i, int j){
	if(i > j) swap(i, j);
	if(is){
		return ans(i, j);
	}
	
	//~ swap(x[i], x[j]);
	//~ swap(y[i], y[j]);
	
	//~ for(int k=i;k<=j;k++){
		//~ if(check(k)) cnt--;
		//~ mnx[k] = mxx[k] = x[k];
		//~ mny[k] = mxy[k] = y[k];
		//~ if(k){
			//~ mnx[k] = min(mnx[k], mnx[k - 1]);
			//~ mny[k] = min(mny[k], mny[k - 1]);
			//~ mxx[k] = max(mxx[k], mxx[k - 1]);
			//~ mxy[k] = max(mxy[k], mxy[k - 1]);
		//~ }
		
		//~ if(check(k)) cnt++;
	//~ }
	
	//~ return cnt;
}

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:195:1: warning: control reaches end of non-void function [-Wreturn-type]
  195 | }
      | ^

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