Submission #595369

#	Time	Username	Problem	Language	Result	Execution time	Memory
595369		FatihSolak	Seats (IOI18_seats)	C++17	100 / 100	3280 ms	165180 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
struct node{
	int val1,val2,cnt,lazy1,lazy2;
	node(){
		val1 = 0,val2 = 0,cnt = 1,lazy1 = 0,lazy2 = 0;
	}
	node(int a){
		val1 = 1e9,val2 = 1e9,cnt = 0,lazy1 = 0,lazy2 = 0;
	}
};
node merge(node a,node b){
	node ret(-1);
	ret.val1 = min(a.val1,b.val1);
	if(a.val1 == ret.val1)
		ret.val2 = min(ret.val2,a.val2);
	if(b.val1 == ret.val1)
		ret.val2 = min(ret.val2,b.val2);
	if(a.val1 == ret.val1 && a.val2 == ret.val2){
		ret.cnt += a.cnt;
	}
	if(b.val1 == ret.val1 && b.val2 == ret.val2){
		ret.cnt += b.cnt;
	}
	return ret;
}
int val1[N],val2[N];
struct SegTree{
	vector<node> t;
	int n;
	void init(int size){
		n = size;
		t.assign(4*n,node());
	}
	void build(int v,int tl,int tr){
		if(tl == tr){
			t[v].val1 = val1[tl];
			t[v].val2 = val2[tl];
			t[v].cnt = 1;
			return;
		}
		int tm = (tl + tr)/2;
		build(v*2,tl,tm);
		build(v*2+1,tm+1,tr);
		t[v] = merge(t[v*2],t[v*2+1]);
	}
	void push(int v){
		t[v*2].val1 += t[v].lazy1;
		t[v*2].val2 += t[v].lazy2;
		t[v*2].lazy1 += t[v].lazy1;
		t[v*2].lazy2 += t[v].lazy2;

		t[v*2+1].val1 += t[v].lazy1;
		t[v*2+1].val2 += t[v].lazy2;
		t[v*2+1].lazy1 += t[v].lazy1;
		t[v*2+1].lazy2 += t[v].lazy2;

		t[v].lazy1 = t[v].lazy2 = 0;

	}
	void upd(int v,int tl,int tr,int l,int r,pair<int,int> val){
		if(tr < l || r < tl)
			return;
		if(l <= tl && tr <= r){
			t[v].val1 += val.first;
			t[v].val2 += val.second;
			t[v].lazy1 += val.first;
			t[v].lazy2 += val.second;
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val);
		upd(v*2+1,tm+1,tr,l,r,val);
		t[v] = merge(t[v*2],t[v*2+1]);
	}
	node get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl)
			return node(-1);
		if(l <= tl && tr <= r){
			return t[v];
		}
		push(v);
		int tm = (tl + tr)/2;
		return merge(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
	}
	void upd(int l,int r,pair<int,int> val){
		if(l > r)return;
		upd(1,1,n,l,r,val);
	}
	void upd(pair<int,int> range,pair<int,int> val){
		upd(range.first,range.second,val);
	}
	node get(int l,int r){
		if(l > r)return node(-1);
		return get(1,1,n,l,r);
	}
};
SegTree tree;
vector<vector<int>> grid;
int n;
vector<int> r,c;
pair<int,int> getw(pair<int,int> a){
	return {1,grid[a.first][a.second] - 1};
}
pair<int,int> getb(pair<int,int> a){
	return {grid[a.first][a.second], n};
}
pair<int,int> intersect(pair<int,int> a,pair<int,int> b){
	return {max(a.first,b.first),min(a.second,b.second)};
}
vector<pair<int,int>> rect(int x,int y){
	vector<pair<int,int>> ret;
	for(int i = 0;i<=1;i++){
		for(int j = 0;j<=1;j++){
			ret.push_back({x+i,y+j});
		}
	}
	return ret;
}
void init1(vector<pair<int,int>> points,int coef){
	for(int i = 0;i<points.size();i++){
		pair<int,int> range = {-1e9,1e9};
		for(int j = 0;j<points.size();j++){
			if(i == j){
				range = intersect(range,getb(points[j]));
			}
			else range = intersect(range,getw(points[j]));
		}
		if(range.first > range.second)continue;
		val1[range.first] += coef;
		val1[range.second + 1] -= coef;
	}
}
void init2(vector<pair<int,int>> points,int coef){
	for(int i = 0;i<points.size();i++){
		pair<int,int> range = {-1e9,1e9};
		for(int j = 0;j<points.size();j++){
			if(i == j){
				range = intersect(range,getw(points[j]));
			}
			else range = intersect(range,getb(points[j]));
		}
		if(range.first > range.second)continue;
		val2[range.first] += coef;
		val2[range.second + 1] -= coef;
	}
}
void upd1(vector<pair<int,int>> points,int coef){
	for(int i = 0;i<points.size();i++){
		pair<int,int> range = {-1e9,1e9};
		for(int j = 0;j<points.size();j++){
			if(i == j){
				range = intersect(range,getb(points[j]));
			}
			else range = intersect(range,getw(points[j]));
		}
		tree.upd(range,{coef,0});
	}
}
void upd2(vector<pair<int,int>> points,int coef){
	for(int i = 0;i<points.size();i++){
		pair<int,int> range = {-1e9,1e9};
		for(int j = 0;j<points.size();j++){
			if(i == j){
				range = intersect(range,getw(points[j]));
			}
			else range = intersect(range,getb(points[j]));
		}
		tree.upd(range,{0,coef});
	}
}
void upd(int x,int y,int coef){
	pair<int,int> range;
	vector<pair<int,int>> points;

	//*.
	//..

	//xa
	//aa
	points = rect(x-1,y-1);
	upd1(points,coef);
	//ax
	//aa
	points = rect(x-1,y);
	upd1(points,coef);
	//aa
	//xa
	points = rect(x,y-1);
	upd1(points,coef);
	//aa
	//ax
	points = rect(x,y);
	upd1(points,coef);


	//.*
	//**


	//xa
	//aa
	points = rect(x-1,y-1);
	upd2(points,coef);
	//ax
	//aa
	points = rect(x-1,y);
	upd2(points,coef);
	//aa
	//xa
	points = rect(x,y-1);
	upd2(points,coef);
	//aa
	//ax
	points = rect(x,y);
	upd2(points,coef);

}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H*W;
	r = R;
	c = C;
	grid = vector<vector<int>> (H+2,vector<int>(W+2,H*W+1));
	tree.init(n);
	for(int i = 0;i<n;i++){
		r[i]++;
		c[i]++;
		grid[r[i]][c[i]] = i+1;
		// upd(r[i],c[i],1);
		// for(int j = 1;j<=n;j++){
		// 	cout << tree.get(j,j).val1 << " " << tree.get(j,j).val2 << " " << tree.get(j,j).cnt << endl;
		// }
		// cout << endl;
	}
	for(int i = 0;i<=H;i++){
		for(int j = 0;j<=W;j++){
			init1(rect(i,j),1);
			init2(rect(i,j),1);
		}
	}
	for(int i = 1;i<=n;i++){
		val1[i] += val1[i-1];
		val2[i] += val2[i-1];
	}
	tree.build(1,1,n);
	// for(int i = 1;i<=n;i++){
	// 	cout << tree.get(i,i).val1 << " " << tree.get(i,i).val2 << " " << tree.get(i,i).cnt << endl;
	// }
}

int swap_seats(int a, int b) {
	upd(r[a],c[a],-1);
	upd(r[b],c[b],-1);
	swap(grid[r[a]][c[a]],grid[r[b]][c[b]]);
	swap(r[a],r[b]);
	swap(c[a],c[b]);
	upd(r[a],c[a],1);
	upd(r[b],c[b],1);
	return tree.get(1,n).cnt;
}

Compilation message (stderr)

seats.cpp: In function 'void init1(std::vector<std::pair<int, int> >, int)':
seats.cpp:124:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i = 0;i<points.size();i++){
      |                ~^~~~~~~~~~~~~~
seats.cpp:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |   for(int j = 0;j<points.size();j++){
      |                 ~^~~~~~~~~~~~~~
seats.cpp: In function 'void init2(std::vector<std::pair<int, int> >, int)':
seats.cpp:138:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for(int i = 0;i<points.size();i++){
      |                ~^~~~~~~~~~~~~~
seats.cpp:140:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |   for(int j = 0;j<points.size();j++){
      |                 ~^~~~~~~~~~~~~~
seats.cpp: In function 'void upd1(std::vector<std::pair<int, int> >, int)':
seats.cpp:152:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for(int i = 0;i<points.size();i++){
      |                ~^~~~~~~~~~~~~~
seats.cpp:154:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for(int j = 0;j<points.size();j++){
      |                 ~^~~~~~~~~~~~~~
seats.cpp: In function 'void upd2(std::vector<std::pair<int, int> >, int)':
seats.cpp:164:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |  for(int i = 0;i<points.size();i++){
      |                ~^~~~~~~~~~~~~~
seats.cpp:166:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |   for(int j = 0;j<points.size();j++){
      |                 ~^~~~~~~~~~~~~~

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