제출 #122312

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

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> r, c;
vector<vector<int> > s;
int cnt[2097152], mn[2097152], lz[2097152];
int L, R, val;

void push(int id, int l, int r){
	mn[id] += lz[id];
	if(l != r){
		lz[id << 1] += lz[id];
		lz[id << 1 | 1] += lz[id];
	}
	lz[id] = 0;
}

void update(int id, int l, int r){
	push(id, l, r);
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		lz[id] += val;
		push(id, l, r);
		return;
	}
	int m = (l + r) >> 1;
	update(id << 1, l, m);
	update(id << 1 | 1, m + 1, r);
	if(mn[id << 1] < mn[id << 1 | 1]){
		mn[id] = mn[id << 1];
		cnt[id] = cnt[id << 1];
	} else if(mn[id << 1] > mn[id << 1 | 1]){
		mn[id] = mn[id << 1 | 1];
		cnt[id] = cnt[id << 1 | 1];
	} else {
		mn[id] = mn[id << 1];
		cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
	}
}

void build(int id, int l, int r){
	if(l == r){
		cnt[id] = 1;
		return;
	}
	int m = (l + r) >> 1;
	build(id << 1, l, m);
	build(id << 1 | 1, m + 1, r);
	cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
}
vector<int> ord;
void order(int a, int b, int c, int d){
	ord = {a, b, c, d};
	sort(ord.begin(), ord.end());
}

int n;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H * W;
	for(int i = 0; i <= H + 1; i++){
		s.push_back(vector<int>(W + 2, n + 1));
	}
	
	r.push_back(0);
	c.push_back(0);
	build(1, 1, n);
	for(int i = 0; i < n; i++){
		R[i]++;
		C[i]++;
		s[R[i]][C[i]] = i + 1;
		c.push_back(C[i]);
		r.push_back(R[i]);
	}
	val = 1;
	for(int i = 0; i <= H; i++){
		for(int j = 0; j <= W; j++){
			order(s[i][j], s[i + 1][j], s[i][j + 1], s[i + 1][j + 1]);
			L = ord[0];
			::R = ord[1] - 1;
			if(L <= ::R)update(1, 1, n);
			L = ord[2];
			::R = ord[3] - 1;
			if(L <= ::R)update(1, 1, n);
		}
	}
}

int dx[] = {1, -1, 1, -1};
int dy[] = {1, 1, -1, -1};

int swap_seats(int a, int b){
	a++; b++;
	val = -1;
	int t[] = {a, b};
	for(int j = 0; j < 2; j++){
		int x = r[t[j]], y = c[t[j]];
		for(int i = 0; i < 4; i++){
		}
	}
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	swap(s[r[a]][c[a]], s[r[b]][c[b]]);
	val = 1;
	for(int j = 0; j < 2; j++){
		int x = r[t[j]], y = c[t[j]];
		for(int i = 0; i < 4; i++){
			order(s[x][y], s[x + dx[i]][y], s[x][y + dy[i]], s[x + dx[i]][y + dy[i]]);
			L = ord[0];
			R = ord[1] - 1;
			if(L <= R) update(1, 1, n);
			L = ord[2];
			R = ord[3] - 1;
			if(L <= R) update(1, 1, n);
		}
	}
	return cnt[1];
}

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

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:97:7: warning: unused variable 'x' [-Wunused-variable]
   int x = r[t[j]], y = c[t[j]];
       ^
seats.cpp:97:20: warning: unused variable 'y' [-Wunused-variable]
   int x = r[t[j]], y = c[t[j]];
                    ^

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