Submission #349299

#	Time	Username	Problem	Language	Result	Execution time	Memory
349299		Kerim	Seats (IOI18_seats)	C++17	100 / 100	1422 ms	123144 KiB

seats

#include "seats.h"
#include "bits/stdc++.h"
#define MAXN 1000009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<int>r,c,delta;
vector<vector<int> >arr;
int h,w,hw;
struct node{
	int mn,sum,cnt;	
}s[MAXN<<2];
node merge(node x,node y){
	node z;z.sum=x.sum+y.sum;z.cnt=0;
	z.mn=min(x.mn,x.sum+y.mn);
	if(x.mn==z.mn)z.cnt+=x.cnt;
	if(x.sum+y.mn==z.mn)z.cnt+=y.cnt;
	return z;	
}
void upd(int p,int v,int nd=1,int x=0,int y=hw-1){
	if(x==y){s[nd].sum=s[nd].mn=v;s[nd].cnt=1;return;}
	int mid=(x+y)>>1;
	if(p<=mid)upd(p,v,nd<<1,x,mid);
	else upd(p,v,nd<<1|1,mid+1,y);
	s[nd]=merge(s[nd<<1],s[nd<<1|1]);
}
void add(int val){
	if(val<0 or val>=hw)return;
	delta[val]=0;
	int x=r[val],y=c[val];
	for(int a=0;a<=1;a++)
		for(int b=0;b<=1;b++){
			int cnt=0;
			for(int i=0;i<=1;i++)
				for(int j=0;j<=1;j++)
					if(arr[x-1+a+i][y-1+b+j]>val)cnt++;
			if(cnt&1)delta[val]++;
			else delta[val]--;
		}
	upd(val,delta[val]);
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C) {
  	r=R;c=C;h=H;w=W;hw=H*W;
  	arr.resize(h+2);delta.resize(hw+2);
  	for(int i=0;i<=h+1;i++)
  		arr[i].resize(w+2);
  	for(int i=0;i<=h+1;i++)
  		for(int j=0;j<=w+1;j++)
  			arr[i][j]=hw;
  	for(int i=0;i<hw;i++)
		arr[++r[i]][++c[i]]=i;
  	for(int i=0;i<hw;i++)add(i);
}
int swap_seats(int a, int b) {
	swap(arr[r[a]][c[a]],arr[r[b]][c[b]]);
	swap(c[a],c[b]);swap(r[a],r[b]);
	for(int i=-1;i<=1;i++)
		for(int j=-1;j<=1;j++)
			add(arr[r[a]+i][c[a]+j]),add(arr[r[b]+i][c[b]+j]);
	return s[1].cnt;
}

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