제출 #765273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765273		ono_de206	Seats (IOI18_seats)	C++14	25 / 100	4083 ms	112044 KiB

seats

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

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define x first
#define y second

const int mxn = 1e6 + 10;
int n, m;

struct node {
	int xMin, xMax, yMin, yMax;
	node(int x1, int y1, int x2, int y2) : xMin(x1), yMin(y1), xMax(x2), yMax(y2) {}
	node(int x, int y) : xMin(x), yMin(y), xMax(x), yMax(y) {}
	node() : xMin(1e9), yMin(1e9), xMax(-1e9), yMax(-1e9) {}
	node operator+(node a) {
		return node(min(a.xMin, xMin), min(a.yMin, yMin), max(a.xMax, xMax), max(a.yMax, yMax));
	}
	bool operator==(node a) {
		return a.xMax == xMax && a.xMin == xMin && a.yMax == yMax && a.yMin == yMin;
	}
};

vector<node> arr;
node d[mxn * 4];

void update(int l, int r, int i, int x, node val) {
	if(l == r) {
		d[i] = val;
		return;
	}
	int m = (l + r) / 2;
	if(x <= m) update(l, m, i * 2, x, val);
	else update(m + 1, r, i * 2 + 1, x, val);
	d[i] = d[i * 2] + d[i * 2 + 1];
}

node get(int l, int r, int i, int x) {
	if(r <= x) return d[i];
	int m = (l + r) / 2;
	if(x <= m) return get(l, m, i * 2, x);
	return d[i * 2] + get(m + 1, r, i * 2 + 1, x);
}

int query(int l, int r, int i, node val) {
	if(l == r) return l + (get(0, n * m - 1, 1, l) == val);
	int m = (l + r) / 2;
	if(val.xMin > d[i * 2].xMin || val.xMax < d[i * 2].xMax || val.yMin > d[i * 2].yMin || val.yMax < d[i * 2].yMax)
		return query(l, m, i * 2, val);
	return query(m + 1, r, i * 2 + 1, val);
}


void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H;
	m = W;
	for(int i = 0; i < n * m; i++) {
		arr.eb(R[i], C[i]);
		update(0, n * m - 1, 1, i, arr[i]);
	}
}

int swap_seats(int a, int b) {
	update(0, n * m - 1, 1, a, arr[b]);
	update(0, n * m - 1, 1, b, arr[a]);
	swap(arr[a], arr[b]);
	node now(1e9, 1e9, -1e9, -1e9);
	int l = -1, ans = 0;
	while(l < n * m) {
		l = query(0, n * m - 1, 1, now);
		if(now.xMax != -1e9 && (now.xMax - now.xMin + 1) * (now.yMax - now.yMin + 1) == l) ans++;
		if(l < n * m) now = get(0, n * m - 1, 1, l);
	}
	return ans;
}

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

seats.cpp: In constructor 'node::node(int, int, int, int)':
seats.cpp:18:18: warning: 'node::yMin' will be initialized after [-Wreorder]
   18 |  int xMin, xMax, yMin, yMax;
      |                  ^~~~
seats.cpp:18:12: warning:   'int node::xMax' [-Wreorder]
   18 |  int xMin, xMax, yMin, yMax;
      |            ^~~~
seats.cpp:19:2: warning:   when initialized here [-Wreorder]
   19 |  node(int x1, int y1, int x2, int y2) : xMin(x1), yMin(y1), xMax(x2), yMax(y2) {}
      |  ^~~~
seats.cpp: In constructor 'node::node(int, int)':
seats.cpp:18:18: warning: 'node::yMin' will be initialized after [-Wreorder]
   18 |  int xMin, xMax, yMin, yMax;
      |                  ^~~~
seats.cpp:18:12: warning:   'int node::xMax' [-Wreorder]
   18 |  int xMin, xMax, yMin, yMax;
      |            ^~~~
seats.cpp:20:2: warning:   when initialized here [-Wreorder]
   20 |  node(int x, int y) : xMin(x), yMin(y), xMax(x), yMax(y) {}
      |  ^~~~
seats.cpp: In constructor 'node::node()':
seats.cpp:18:18: warning: 'node::yMin' will be initialized after [-Wreorder]
   18 |  int xMin, xMax, yMin, yMax;
      |                  ^~~~
seats.cpp:18:12: warning:   'int node::xMax' [-Wreorder]
   18 |  int xMin, xMax, yMin, yMax;
      |            ^~~~
seats.cpp:21:2: warning:   when initialized here [-Wreorder]
   21 |  node() : xMin(1e9), yMin(1e9), xMax(-1e9), yMax(-1e9) {}
      |  ^~~~

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