Submission #419212

#	Time	Username	Problem	Language	Result	Execution time	Memory
419212		peuch	Seats (IOI18_seats)	C++17	5 / 100	4072 ms	103452 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 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);
	for(int i = 0; i < r.size(); i++)
		update(1, 0, h * w - 1, i, node(r[i], r[i], c[i], c[i]));
}

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 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); 
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < r.size(); i++)
      |                 ~~^~~~~~~~~~
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