제출 #419216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419216		peuch	자리 배치 (IOI18_seats)	C++17	5 / 100	4067 ms	86832 KiB

seats

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

const int MAXN = 1e6 + 10;
const int MAXW = 1e3 + 10;

struct node{
	int minx, maxx, miny, maxy;
	node(int _minx = MAXN, int _maxx = -1, int _miny = MAXN, int _maxy = -1){
		minx = _minx;
		maxx = _maxx;
		miny = _miny;
		maxy = _maxy;
	}
	node operator + (node a){
		node ret;
		ret.minx = min(minx, a.minx);
		ret.maxx = max(maxx, a.maxx);
		ret.miny = min(miny, a.miny);
		ret.maxy = max(maxy, a.maxy);
		return ret;
	}
	void print(){
		printf("%d %d %d %d\n", minx, maxx, miny, maxy);
	}
};

vector<int> r, c;
int h, w;

vector<node> seg;

void build(int pos, int ini, int fim);
void update(int pos, int ini, int fim, int id, node val);
node query(int pos, int ini, int fim, int p, int q);

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	r = R, c = C;
	h = H, w = W;
	seg = vector<node> (4 * h * w);
	build(1, 0, h * w - 1);
}

int swap_seats(int a, int b) {
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	update(1, 0, h * w - 1, a, node(r[a], r[a], c[a], c[a]));
	update(1, 0, h * w - 1, b, node(r[b], r[b], c[b], c[b]));
	int cur = 0;
	int maxi = 0;
	int maxr = r[0], minr = r[0], maxc = c[0], minc = c[0];
	int ret = 0;
	while(cur < h * w){
		node val = query(1, 0, h * w - 1, 0, cur);
		minr = val.minx;
		maxr = val.maxx;
		minc = val.miny;
		maxc = val.maxy;
		if(cur == (maxr - minr + 1) * (maxc - minc + 1) - 1) ret++, cur++;
		else cur = (maxr - minr + 1) * (maxc - minc + 1) - 1;
	}
	return ret;
}

void build(int pos, int ini, int fim){
	if(ini == fim){
		seg[pos] = node(r[ini], r[ini], c[ini], c[ini]);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	build(e, ini, mid);
	build(d, mid + 1, fim);
	seg[pos] = seg[e] + seg[d];
}

void update(int pos, int ini, int fim, int id, node val){
	if(ini > id || fim < id) return;
	if(ini == fim){
		seg[pos] = val;
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	update(e, ini, mid, id, val);
	update(d, mid + 1, fim, id, val);
	seg[pos] = seg[e] + seg[d];
}

node query(int pos, int ini, int fim, int p, int q){
	if(ini > q || fim < p) return node();
	if(ini >= p && fim <= q) return seg[pos];
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	return query(e, ini, mid, p, q) + query(d, mid + 1, fim, p, q); 
}

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

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:51:6: warning: unused variable 'maxi' [-Wunused-variable]
   51 |  int maxi = 0;
      |      ^~~~

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