Submission #674398

#	Time	Username	Problem	Language	Result	Execution time	Memory
674398		alvingogo	Seats (IOI18_seats)	C++14	100 / 100	2683 ms	142080 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int h,w;
vector<vector<int> > val;
vector<pair<int,int> > y;
int n;

struct ST{
	struct no{
		int mn=0,cnt=1,tag=0;
	};
	vector<no> st;
	void init(int x){
		st.resize(4*x);
	}
	void upd(int v,int k){
		st[v].mn+=k;
		st[v].tag+=k;
	}
	void pudo(int v){
		upd(2*v+1,st[v].tag);
		upd(2*v+2,st[v].tag);
		st[v].tag=0;
	}
	void pull(int v){
		st[v].mn=min(st[2*v+1].mn,st[2*v+2].mn);
		st[v].cnt=0;
		if(st[2*v+1].mn==st[v].mn){
			st[v].cnt+=st[2*v+1].cnt;
		}
		if(st[2*v+2].mn==st[v].mn){
			st[v].cnt+=st[2*v+2].cnt;
		}
	}
	void update(int v,int L,int R,int l,int r,int k){
		if(r<l){
			return;
		}
		if(L==l && r==R){
			upd(v,k);
			return;
		}
		pudo(v);
		int m=(L+R)/2;
		if(r<=m){
			update(2*v+1,L,m,l,r,k);
		}
		else if(l>m){
			update(2*v+2,m+1,R,l,r,k);
		}
		else{
			update(2*v+1,L,m,l,m,k);
			update(2*v+2,m+1,R,m+1,r,k);
		}
		pull(v);
	}
	int query(){
		return st[0].cnt;
	}
}st;

void ud(int a,int b,int c,int d,int k){
	vector<int> g{a,b,c,d};
	sort(g.begin(),g.end());
	st.update(0,0,n-1,g[0],g[1]-1,k);
	st.update(0,0,n-1,g[2],g[3]-1,k); 
}
inline void chg(int i,int j,int t){
	ud(val[i][j],val[i+1][j],val[i+1][j+1],val[i][j+1],t);
}
void give_initial_chart(int a,int b,vector<int> r,vector<int> c){
	h=a;
	w=b;
	val.clear();
	val.resize(h+2,vector<int>(w+2,h*w));
	n=h*w+1;
	st.init(n);
  st.update(0,0,n-1,n-1,n-1,1e9);
	for(int i=0;i<h*w;i++){
		val[r[i]+1][c[i]+1]=i;
		y.push_back({r[i]+1,c[i]+1});
	}
	for(int i=0;i<=h;i++){
		for(int j=0;j<=w;j++){
			chg(i,j,1);
		}
	}
}

const int dx[4]={0,0,-1,-1};
const int dy[4]={0,-1,0,-1};
int swap_seats(int a,int b){
	auto c=y[a];
	auto d=y[b];
	for(int i=0;i<4;i++){
		chg(c.fs+dx[i],c.sc+dy[i],-1);
    chg(d.fs+dx[i],d.sc+dy[i],-1);
	}
	swap(val[c.fs][c.sc],val[d.fs][d.sc]);
	for(int i=0;i<4;i++){
		chg(c.fs+dx[i],c.sc+dy[i],1);
    chg(d.fs+dx[i],d.sc+dy[i],1);
	}
	swap(y[a],y[b]);
	return st.query();
}

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