Submission #379370

#	Time	Username	Problem	Language	Result	Execution time	Memory
379370		autumn_eel	Seats (IOI18_seats)	C++14	5 / 100	4086 ms	89608 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

const int INF=0x3f3f3f3f;

struct Segtree1{ //1D
	int N;
	vector<int>dat;

	Segtree1(){}
	
	Segtree1(int n){
		N=1;while(N<n)N<<=1;
		dat=vector<int>(2*N);
	}

	void update(int k,int x){
		k+=N;dat[k]=x;
		while(k>1){
			k>>=1;
			dat[k]=max(dat[k*2],dat[k*2+1]);
		}
	}

	int query(int l,int r){
		int res=0;
		for(l+=N,r+=N;l<r;l>>=1,r>>=1){
			if(l&1)res=max(res,dat[l++]);
			if(r&1)res=max(res,dat[--r]);
		}
		return res;
	}
};

struct Segtree2{ //2D
	int H,W;
	vector<Segtree1>dat;

	Segtree2(){}
	
	Segtree2(int h,int w){
		H=1;while(H<h)H<<=1;
		W=1;while(W<w)W<<=1;
		dat=vector<Segtree1>(2*H,Segtree1(W));
	}
	
	void update(int x,int y,int val){
		x+=H;dat[x].update(y,val);
		while(x>1){
			x>>=1;
			dat[x].update(y,max(dat[x*2].query(y,y+1),dat[x*2+1].query(y,y+1)));
		}
	}

	int query(int l1,int r1,int l2,int r2){
		int res=0;
		for(l1+=H,r1+=H;l1<r1;l1>>=1,r1>>=1){
			if(l1&1)res=max(res,dat[l1++].query(l2,r2));
			if(r1&1)res=max(res,dat[--r1].query(l2,r2));
		}
		return res;
	}
};

struct Segtree{
	int N;
	vector<int>dat;
	function<int(int,int)>f;
	int ini;

	Segtree(){}
	
	Segtree(int n,int ini,function<int(int,int)>f):ini(ini),f(f){
		N=1;while(N<n)N<<=1;
		dat=vector<int>(2*N,ini);
	}

	void update(int k,int x){
		k+=N;dat[k]=x;
		while(k>1){
			k>>=1;
			dat[k]=f(dat[k*2],dat[k*2+1]);
		}
	}

	int query(int l,int r){
		int res=ini;
		for(l+=N,r+=N;l<r;l>>=1,r>>=1){
			if(l&1)res=f(res,dat[l++]);
			if(r&1)res=f(res,dat[--r]);
		}
		return res;
	}

};

static int h,w;
static vector<int>r,c;

Segtree2 range;
Segtree rmin,rmax,cmin,cmax;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	rmin=cmin=Segtree(H*W,INF,[](int a,int b){return min(a,b);});
	rmax=cmax=Segtree(H*W,0,[](int a,int b){return max(a,b);});

	range=Segtree2(H,W);
	
	h=H;w=W;
	r=R;c=C;

	rep(i,h*w){
		rmin.update(i,r[i]);
		rmax.update(i,r[i]);
		cmin.update(i,c[i]);
		cmax.update(i,c[i]);

		range.update(r[i],c[i],i);
	}	
}

int swap_seats(int a, int b) {
	if(a>b)swap(a,b);
	swap(r[a],r[b]);
	swap(c[a],c[b]);

	rmin.update(a,r[a]);
	rmin.update(b,r[b]);

	rmax.update(a,r[a]);
	rmax.update(b,r[b]);

	cmin.update(a,c[a]);
	cmin.update(b,c[b]);

	cmax.update(a,c[a]);
	cmax.update(b,c[b]);

	range.update(r[a],c[a],a);
	range.update(r[b],c[b],b);

	int ans=0;
	int cur=0;

	while(cur<h*w){
		int l1=rmin.query(0,cur+1),r1=rmax.query(0,cur+1)+1;
		int l2=cmin.query(0,cur+1),r2=cmax.query(0,cur+1)+1;

		int val=range.query(l1,r1,l2,r2);

		assert(val>=cur);

		if(val==cur){
			ans++;
			cur++;
			continue;
		}

		cur=val;
	}

	return ans;
}

Compilation message (stderr)

seats.cpp: In constructor 'Segtree::Segtree(int, int, std::function<int(int, int)>)':
seats.cpp:71:6: warning: 'Segtree::ini' will be initialized after [-Wreorder]
   71 |  int ini;
      |      ^~~
seats.cpp:70:24: warning:   'std::function<int(int, int)> Segtree::f' [-Wreorder]
   70 |  function<int(int,int)>f;
      |                        ^
seats.cpp:75:2: warning:   when initialized here [-Wreorder]
   75 |  Segtree(int n,int ini,function<int(int,int)>f):ini(ini),f(f){
      |  ^~~~~~~

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