Submission #521123

#	Time	Username	Problem	Language	Result	Execution time	Memory
521123		sofapuden	Seats (IOI18_seats)	C++14	11 / 100	4032 ms	202132 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){
		if(l > r)return;
		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;
map<pair<int,int>,int> M;

void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
	R = r;
	C = c;
	vector<int> v(H*W);
	int cu = -4;
	set<pair<int,int>> S;
	for(int i = 0; i < H*W; ++i){
		S.insert({R[i],C[i]});
		M[make_pair(R[i],C[i])] = i+1;
		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){
						cn+=S.count({x1+x2+R[i],y1+y2+C[i]});
					}
				}
				if(cn&1)cu++;
				else cu--;
			}
		}
		v[i] = cu;
	}
	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(M[make_pair(x1+x2+R[a],y1+y2+C[a])])z.push_back(M[make_pair(x1+x2+R[a],y1+y2+C[a])]-1);
				}
			}
			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(M[make_pair(x1+x2+R[b],y1+y2+C[b])])z.push_back(M[make_pair(x1+x2+R[b],y1+y2+C[b])]-1);
				}
			}
			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(M[{R[a],C[a]}],M[{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(M[make_pair(x1+x2+R[a],y1+y2+C[a])])z.push_back(M[make_pair(x1+x2+R[a],y1+y2+C[a])]-1);
				}
			}
			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(M[make_pair(x1+x2+R[b],y1+y2+C[b])])z.push_back(M[make_pair(x1+x2+R[b],y1+y2+C[b])]-1);
				}
			}
			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: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30