Submission #601964

#	Time	Username	Problem	Language	Result	Execution time	Memory
601964		idiot123	Seats (IOI18_seats)	C++14	0 / 100	656 ms	80824 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;
int n;
vector<pair<int, int>> v;

class InfoTree{
	private:
	int lrSize = 2;
	vector<int> minR;
	vector<int> maxR;
	vector<int> minC;
	vector<int> maxC;
	
	void update(int pos, bool up){
		minR[pos] = min(minR[2*pos], minR[2*pos+1]);
		maxR[pos] = max(maxR[2*pos], maxR[2*pos + 1]);
		minC[pos] = min(minC[2*pos], minC[2*pos + 1]);
		maxC[pos] = max(maxC[2*pos], maxC[2*pos + 1]);
		if(up && pos > 1)update(pos/2, true);
	}
	
	
	//minR, maxR, minC, maxC
	array<int, 4> rangeInfo(int a, int b, int l, int r, int pos){
		if(b < l || r  < a)return {INF, -INF, INF, -INF};
		if(a <= l && r <= b){
			return {minR[pos], maxR[pos], minC[pos], maxC[pos]};
		}else{
			int m = (l + r) / 2;
			array<int, 4> ans1 = rangeInfo(a, b, l, m, 2*pos);
			array<int, 4> ans2 = rangeInfo(a, b, m+1, r, 2*pos + 1);
			return {min(ans1[0], ans2[0]), max(ans1[1], ans2[1]), min(ans1[2], ans2[2]), max(ans1[3], ans2[3])};
		}
	}
	
	public:
	
	InfoTree(){};
	
	void resize(vector<pair<int, int>>& v){
		while(lrSize < v.size())lrSize *= 2;
		minR.resize(2*lrSize, INF); maxR.resize(2*lrSize, -INF);
		minC.resize(2*lrSize, INF); maxC.resize(2*lrSize, -INF);
		for(int i =0; i < v.size(); i++){
			minR[lrSize + i] = maxR[lrSize + i] = v[i].first;
			minC[lrSize + i] = maxC[lrSize + i] = v[i].second;
		}
		for(int j = lrSize - 1; j >= 1; j--)update(j, false);
	}
	
	void set(int pos, int r, int c){
		pos += lrSize;
		minR[pos] = maxR[pos] = r;
		minC[pos] = maxC[pos] = c;
		update(pos/2, true);
	}
	
	array<int, 4> getInfo(int a, int b){
		return rangeInfo(a, b, 0, lrSize - 1, 1);
	}
};

InfoTree infoTree;

class SumTree{
	private:
	int lrSize = 2;
	vector<int> v;
	
	void update(int pos){
		v[pos] = v[2*pos] + v[2*pos + 1];
	}
	
	void push(int pos){
		if(v[pos] == 0){
			v[2*pos] = v[2*pos + 1] = 0;
		}
	}
	
	void rangeClear(int a, int b, int l, int r, int pos){
		if(b < l || r < a)return;
		if(a <= l && r <= b){
			v[pos] = 0;
		}else{
			int m = (l + r)/2;
			rangeClear(a, b, l, m, 2*pos);
			rangeClear(a, b, m+1, r, 2*pos + 1);
		}
	}
	
	public:
	
	SumTree(){}
	
	void resize(){
		while(lrSize < n)lrSize *= 2;
		v.resize(2*lrSize, 0);
	}
	
	void add(int pos){
		pos += lrSize;
		vector<int> path;
		while(pos >= 1){
			path.push_back(pos);
			pos /= 2;
		}
		for(int i = path.size() - 1; i >= 1; i--){
			push(path[i]);
		}
		v[path[0]] = 1;
		for(int i = 1; i < path.size(); i++)update(path[i]);
	}
	
	int getAns(){
		return v[1];
	}
	
	void clear(int a, int b){
		rangeClear(a, b, 0, lrSize-1, 1);
	}
};

SumTree sumTree;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H * W;
	v.resize(n);
	for(int i = 0; i < n; i++)v[i] = {R[i], C[i]};
	infoTree.resize(v);
	sumTree.resize();
	int current = 0;
	while(current < n){
		array<int, 4> info = infoTree.getInfo(0, current);
		int h = info[1] - info[0] + 1; int w = info[3] - info[2] + 1;
		if(h * w == current + 1){
			sumTree.add(current);
			current += min(h, w);
		}else{
			current = h * w - 1;
		}
	}
}

int swap_seats(int a, int b) {
	if(a > b)swap(a, b);
	sumTree.clear(a, b-1);
	pair<int, int> p = v[a];
	v[a] = v[b];
	v[b] = p;
	infoTree.set(a, v[a].first, v[a].second);
	infoTree.set(b, v[b].first, v[b].second);
	int current = a;
	while(current < b){
		array<int, 4> info = infoTree.getInfo(0, current);
		int h = info[1] - info[0] + 1; int w = info[3] - info[2] + 1;
		if(h * w == current + 1){
			sumTree.add(current);
			current += min(h, w);
		}else{
			current = h * w - 1;
		}
	}
	return sumTree.getAns();
}

Compilation message (stderr)

seats.cpp: In member function 'void InfoTree::resize(std::vector<std::pair<int, int> >&)':
seats.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   while(lrSize < v.size())lrSize *= 2;
      |         ~~~~~~~^~~~~~~~~~
seats.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i =0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
seats.cpp: In member function 'void SumTree::add(int)':
seats.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for(int i = 1; i < path.size(); i++)update(path[i]);
      |                  ~~^~~~~~~~~~~~~

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