Submission #831562

#	Time	Username	Problem	Language	Result	Execution time	Memory
831562		tolbi	Seats (IOI18_seats)	C++17	5 / 100	4072 ms	65468 KiB

seats

#include <bits/stdc++.h>
using namespace std;
#include "seats.h"
#define tol(bi) (1LL<<((int)(bi)))
const int LIMN=1e9;
const int LIMM=1e9;
vector<int> R,C;
struct SegTree2DMax{
	struct SegTreeMax{
		vector<int> segtree;
		SegTreeMax(int n){
			segtree.resize(tol(ceil(log2(n)+1))-1,23232323);
		}
		void update(int node, int val){
			node+=segtree.size()/2;
			segtree[node]=val;
			while (node){
				node=(node-1)/2;
				segtree[node]=max(segtree[node*2+1],segtree[node*2+2]);
			}
		}
		int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
			if (r==-1) r = segtree.size()/2;
			if (l>=tarl && r<=tarr) return segtree[node];
			if (l>tarr || r<tarl) return 0;
			int mid = l+(r-l)/2;
			int lnode = query(tarl, tarr, l, mid, node*2+1);
			int rnode = query(tarl, tarr, mid+1, r, node*2+2);
			return max(lnode, rnode);
		}
	};
	vector<SegTreeMax> segtree;
	SegTree2DMax(){}
	void init(int n, int m){
		segtree.resize(tol(ceil(log2(n)+1))-1,m);
	}
	void update(int node, int x, int val){
		node+=segtree.size()/2;
		segtree[node].update(x,val);
		while (node){
			node=(node-1)/2;
			int lnode = segtree[node*2+1].segtree[x+segtree[node*2+1].segtree.size()/2];
			int rnode = segtree[node*2+2].segtree[x+segtree[node*2+2].segtree.size()/2];
			segtree[node].update(x,max(lnode, rnode));
		}
	}
	int query(int tarl, int tarr, int xl, int xr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tarl && r<=tarr) return segtree[node].query(xl,xr);
		if (l>tarr || r<tarl) return 0;
		int mid = l+(r-l)/2;
		int lnode = query(tarl, tarr, xl, xr, l, mid, node*2+1);
		int rnode = query(tarl, tarr, xl, xr, mid+1, r, node*2+2);
		return max(lnode, rnode);
	}
};
struct SegTree2DMin{
	struct SegTreeMin{
		vector<int> segtree;
		SegTreeMin(int n){
			segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
		}
		void update(int node, int val){
			node+=segtree.size()/2;
			segtree[node]=val;
			while (node){
				node=(node-1)/2;
				segtree[node]=min(segtree[node*2+1],segtree[node*2+2]);
			}
		}
		int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
			if (r==-1) r = segtree.size()/2;
			if (l>=tarl && r<=tarr) return segtree[node];
			if (l>tarr || r<tarl) return 23232323;
			int mid = l+(r-l)/2;
			int lnode = query(tarl, tarr, l, mid, node*2+1);
			int rnode = query(tarl, tarr, mid+1, r, node*2+2);
			return min(lnode, rnode);
		}
	};
	vector<SegTreeMin> segtree;
	SegTree2DMin(){}
	void init(int n, int m){
		segtree.resize(tol(ceil(log2(n)+1))-1,m);
	}
	void update(int node, int x, int val){
		node+=segtree.size()/2;
		segtree[node].update(x,val);
		while (node){
			node=(node-1)/2;
			int lnode = segtree[node*2+1].query(x,x);
			int rnode = segtree[node*2+2].query(x,x);
			segtree[node].update(x,min(lnode, rnode));
		}
	}
	int query(int tarl, int tarr, int xl, int xr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tarl && r<=tarr) return segtree[node].query(xl,xr);
		if (l>tarr || r<tarl) return 23232323;
		int mid = l+(r-l)/2;
		int lnode = query(tarl, tarr, xl, xr, l, mid, node*2+1);
		int rnode = query(tarl, tarr, xl, xr, mid+1, r, node*2+2);
		return min(lnode, rnode);
	}
};
SegTree2DMin segtreemin;
SegTree2DMax segtreemax;
int H,W;
void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C) {
	R=_R,C=_C;
	H=_H,W=_W;
	segtreemin.init(H,W);
	segtreemax.init(H,W);
	for (int i = 0; i < R.size(); ++i)
	{
		segtreemin.update(R[i],C[i],i);
		segtreemax.update(R[i],C[i],i);
	}
}
int swap_seats(int a, int b) {
	swap(R[a],R[b]);
	swap(C[a],C[b]);
	segtreemin.update(R[a],C[a],a);
	segtreemax.update(R[a],C[a],a);
	segtreemin.update(R[b],C[b],b);
	segtreemax.update(R[b],C[b],b);
	int crmax = 0;
	int ans = 1;
	int xl=R[0],xr=R[0];
	int yl=C[0],yr=C[0];
	while (xl>0 || xr<H-1 || yl>0 || yr<W-1){
		int minel = 23232323;
		if (xl>0) minel=min(minel,segtreemin.query(0,xl-1,0,W-1));
		if (xr+1<H) minel=min(minel,segtreemin.query(xr+1,H-1,0,W-1));
		if (yl>0) minel=min(minel,segtreemin.query(xl,xr,0,yl-1));
		if (yr+1<W) minel=min(minel,segtreemin.query(xl,xr,yr+1,W-1));
		xr=max(xr,R[minel]);
		xl=min(xl,R[minel]);
		yr=max(yr,C[minel]);
		yl=min(yl,C[minel]);
		crmax=segtreemax.query(xl,xr,yl,yr);
		if ((xr-xl+1)*(yr-yl+1)==crmax+1) ans++;
	}
	return ans;
}

Compilation message (stderr)

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

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