Submission #139702

#	Time	Username	Problem	Language	Result	Execution time	Memory
139702		hamzqq9	Seats (IOI18_seats)	C++14	100 / 100	3059 ms	135836 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((ll)(bas+son)/2)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 1000000000000
#define N 1000005
#define MOD 998244353
using namespace std;

int h,w;
int ww[4][2]={1,1,-1,-1,-1,1,1,-1};
vector<vector<int>> a;
vector<int> r,c;
iii S[N*4];
ii lazy[N*4];

int eval() {

	if(S[1].st.st==4 && S[1].st.nd==0) return S[1].nd;

	return 0;

}

void shift(int node,ii lz) {

	S[node].st.st+=lz.st;
	S[node].st.nd+=lz.nd;
	
	lazy[node].st+=lz.st;
	lazy[node].nd+=lz.nd;

}

void push(int node) {

	shift(node<<1,lazy[node]);
	shift(node<<1|1,lazy[node]);

	lazy[node]={0,0};

}

iii merge(iii a,iii b) {

	if(a.st<b.st) return a;
	if(b.st<a.st) return b;

	return {a.st,a.nd+b.nd};

}

void up(int node,int bas,int son,int l,int r,ii lz) {

	if(bas>r || son<l) return ;

	if(bas>=l && son<=r) {

		shift(node,lz);

		return ;

	}

	push(node);

	up(node<<1,bas,orta,l,r,lz);
	up(node<<1|1,orta+1,son,l,r,lz);

	S[node]=merge(S[node<<1],S[node<<1|1]);

}

void build(int node,int bas,int son) {

	if(bas==son) {

		S[node]={{0,0},1};

		return ;

	}

	build(node<<1,bas,orta);
	build(node<<1|1,orta+1,son);

	S[node]=merge(S[node<<1],S[node<<1|1]);

}

int gtot(int xa,int ya,int xb,int yb) {

	int tot=0;

	if(xa>xb) swap(xa,xb);
	if(ya>yb) swap(ya,yb);

	for(int i=xa;i<=xb;i++) {

		for(int j=ya;j<=yb;j++) {

			tot+=(a[i][j]!=-1);

		}

	}

	return tot;

}

void upd(int x,int y,int val,int sg) {

	if(val==-1) return ;

	int cnt[2][2]={0};

	for(int i=0;i<4;i++) {

		int tot=gtot(x+ww[i][0],y+ww[i][1],x,y);

		if(tot==1) cnt[0][0]++;
		if(tot==3) cnt[0][1]++;

	}

	a[x][y]=val;

	for(int i=0;i<4;i++) {

		int tot=gtot(x+ww[i][0],y+ww[i][1],x,y);

		if(tot==1) cnt[1][0]++;
		if(tot==3) cnt[1][1]++;

	}

	up(1,0,h*w-1,val,h*w-1,{sg*(cnt[1][0]-cnt[0][0]),sg*(cnt[1][1]-cnt[0][1])});

}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {

	h=H;
	w=W;

	a=vector<vector<int>>(h+5,vector<int>(w+5,-1));
	r=c=vector<int>(h*w+5);

	build(1,0,h*w-1);

	for(int i=0;i<h*w;i++) {

		r[i]=R[i]+1;
		c[i]=C[i]+1;

		upd(r[i],c[i],i,1);

	}

}

void upcr(int x,vector<pair<int,ii>>&cr) {

	for(int i=r[x]-1;i<=r[x]+1;i++) {

		for(int j=c[x]-1;j<=c[x]+1;j++) {

			cr.pb({a[i][j],{i,j}});

		}

	}

}

void make_minus(vector<pair<int,ii>>& cr) {

	for(auto x:cr) a[x.nd.st][x.nd.nd]=-1;

}

int swap_seats(int x, int y) {

	#define iii pair<int,ii>

	vector<iii> cr;

	upcr(x,cr);
	upcr(y,cr);

	sort(cr.begin(),cr.end());

	cr.erase(unique(cr.begin(),cr.end()),cr.end());

	make_minus(cr);

	for(auto x:cr) {

		upd(x.nd.st,x.nd.nd,x.st,-1);

	}

	swap(r[x],r[y]);
	swap(c[x],c[y]);

	for(auto& x:cr) {

		tie(x.nd.st,x.nd.nd)={r[x.st],c[x.st]};

	}

	make_minus(cr);

	for(auto x:cr) {

		upd(x.nd.st,x.nd.nd,x.st,1);

	}

	return eval();

}

Compilation message (stderr)

seats.cpp:195:0: warning: "iii" redefined
  #define iii pair<int,ii>
 
seats.cpp:8:0: note: this is the location of the previous definition
 #define iii pair<ii,int>

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