Submission #521127

#	Time	Username	Problem	Language	Result	Execution time	Memory
521127		sofapuden	Seats (IOI18_seats)	C++14	100 / 100	1850 ms	193132 KiB

seats

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

using namespace std;

struct nod{
	int lo, am;
	nod() {}
	nod(int _lo, int _am) : lo(_lo), am(_am) {}
};

struct seg{
	int n;
	vector<nod> st;
	vector<int> A, lazy;
	seg(int sz) : n(sz), st(4*n), lazy(4*n) {}
	seg(vector<int> ini) : seg((int)ini.size()) {
		A = ini;
		build(0,n-1,1);
	}

	nod mer(nod a, nod b){
		nod c(min(a.lo,b.lo),0);
		if(a.lo == c.lo)c.am+=a.am;
		if(b.lo == c.lo)c.am+=b.am;
		return c;
	}

	void build(int l, int r, int p){
		if(l == r){
			nod c(A[l],1);
			st[p] = c;
			return;
		}
		int m = (l+r)>>1;
		build(l,m,p<<1);
		build(m+1,r,(p<<1)+1);
		st[p] = mer(st[p<<1],st[(p<<1)+1]);
	}

	void prop(int p){
		if((p<<1)+1 < (int)lazy.size()){
			lazy[p<<1]+=lazy[p];
			lazy[(p<<1)+1]+=lazy[p];
		}
		lazy[p] = 0;
	}

	void update(int l, int r, int val, int lb, int rb, int p){
		st[p].lo+=lazy[p];
		prop(p);
		if(lb > r || rb < l)return;
		if(lb >= l && rb <= r){
			lazy[p] += val;
			st[p].lo+=lazy[p];
			prop(p);
			return;
		}
		int m = (lb+rb)>>1;
		update(l,r,val,lb,m,p<<1);
		update(l,r,val,m+1,rb,(p<<1)+1);
		st[p] = mer(st[p<<1],st[(p<<1)+1]);
	}
	void print(int l, int r, int p){
		st[p].lo+=lazy[p];
		prop(p);
		if(l == r){
			cout << st[p].lo << ' ';
			return;
		}
		int m = (l+r)>>1;
		print(l,m,p<<1);
		print(m+1,r,(p<<1)+1);
	}
};

seg ST(0);
vector<int> R, C;
int h, w;
vector<vector<int>> gr;

bool inside(int x, int y){
	return x >= 0 && x < h && y >= 0 && y < w;
}

void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
	R = r;
	C = c;
	h = H;
	w = W;
	vector<int> v(H*W);
	vector<vector<int>> GR(H,vector<int>(W,-1));
	int cu = -4;
	for(int i = 0; i < H*W; ++i){
		GR[R[i]][C[i]] = i;
		for(int x1 = -1; x1 <= 0; ++x1){
			for(int y1 = -1; y1 <= 0; ++y1){
				int cn = 0;
				for(int x2 = 0; x2 < 2; ++x2){
					for(int y2 = 0; y2 < 2; ++y2){
						if(inside(x1+x2+R[i],y1+y2+C[i]))cn+=(GR[x1+x2+R[i]][y1+y2+C[i]] != -1);
					}
				}
				if(cn&1)cu++;
				else cu--;
			}
		}
		v[i] = cu;
	}
	gr = GR;
	ST = seg(v);
}

int swap_seats(int a, int b) {
	int n = (int)R.size();
	for(int x1 = -1; x1 <= 0; ++x1){
		for(int y1 = -1; y1 <= 0; ++y1){
			vector<int> z;
			for(int x2 = 0; x2 < 2; ++x2){
				for(int y2 = 0; y2 < 2; ++y2){
					if(inside(x1+x2+R[a],y1+y2+C[a]))z.push_back(gr[x1+x2+R[a]][y1+y2+C[a]]);
				}
			}
			sort(z.begin(),z.end());
			z.push_back(n);
			for(int i = 0; i < (int)z.size()-1; i+=2){
				ST.update(z[i],z[i+1]-1,(i&1 ? 1 : -1),0,n-1,1);
			}
		}
	}
	for(int x1 = -1; x1 <= 0; ++x1){
		for(int y1 = -1; y1 <= 0; ++y1){
			vector<int> z;
			for(int x2 = 0; x2 < 2; ++x2){
				for(int y2 = 0; y2 < 2; ++y2){
					if(inside(x1+x2+R[b],y1+y2+C[b]))z.push_back(gr[x1+x2+R[b]][y1+y2+C[b]]);
				}
			}
			sort(z.begin(),z.end());
			z.push_back(n);
			for(int i = 0; i < (int)z.size()-1; i+=2){
				ST.update(z[i],z[i+1]-1,(i&1 ? 1 : -1),0,n-1,1);
			}
		}
	}
	swap(gr[R[a]][C[a]],gr[R[b]][C[b]]);
	swap(R[a],R[b]);
	swap(C[a],C[b]);
	for(int x1 = -1; x1 <= 0; ++x1){
		for(int y1 = -1; y1 <= 0; ++y1){
			vector<int> z;
			for(int x2 = 0; x2 < 2; ++x2){
				for(int y2 = 0; y2 < 2; ++y2){
					if(inside(x1+x2+R[a],y1+y2+C[a]))z.push_back(gr[x1+x2+R[a]][y1+y2+C[a]]);
				}
			}
			sort(z.begin(),z.end());
			z.push_back(n);
			for(int i = 0; i < (int)z.size()-1; i+=2){
				ST.update(z[i],z[i+1]-1,(i&1 ? -1 : 1),0,n-1,1);
			}
		}
	}
	for(int x1 = -1; x1 <= 0; ++x1){
		for(int y1 = -1; y1 <= 0; ++y1){
			vector<int> z;
			for(int x2 = 0; x2 < 2; ++x2){
				for(int y2 = 0; y2 < 2; ++y2){
					if(inside(x1+x2+R[b],y1+y2+C[b]))z.push_back(gr[x1+x2+R[b]][y1+y2+C[b]]);
				}
			}
			sort(z.begin(),z.end());
			z.push_back(n);
			for(int i = 0; i < (int)z.size()-1; i+=2){
				ST.update(z[i],z[i+1]-1,(i&1 ? -1 : 1),0,n-1,1);
			}
		}
	}
	return ST.st[1].am;
}

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