Submission #819945

#	Time	Username	Problem	Language	Result	Execution time	Memory
819945		ttamx	Seats (IOI18_seats)	C++14	0 / 100	4062 ms	48512 KiB

seats

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

using namespace std;

typedef pair<int,int> p2;

const int N=1e6+5;
const int K=(1<<21)+5;
const int inf=1e9;

int h,w,n;
int r[N],c[N];
int val[N];
int pref[N];

int calc(int x){
	int res=0;
	res+=val[x]>val[x-1]?-1:1;
	res+=val[x]>val[x+1]?-1:1;
	return res;
}

struct segtree{
	struct node{
		int val,freq;
		node():val(inf),freq(0){}
		node(int val,int freq=1):val(val),freq(freq){}
		friend node operator+(node a,node b){
			if(a.val<b.val)return a;
			if(b.val<a.val)return b;
			return node(a.val,a.freq+b.freq);
		}
	}t[K];
	int lz[K];
	void pushlz(int l,int r,int i){
		t[i].val+=lz[i];
		if(l<r){
			lz[i*2]+=lz[i];
			lz[i*2+1]+=lz[i];
		}
		lz[i]=0;
	}
	void build(int l,int r,int i){
		if(l==r)return void(t[i]=node(pref[l]));
		int m=(l+r)/2;
		build(l,m,i*2);
		build(m+1,r,i*2+1);
		t[i]=t[i*2]+t[i*2+1];
	}
	void build(){
		build(1,n,1);
	}
	void update(int l,int r,int i,int x,int y,int v){
		pushlz(l,r,i);
		if(y<l||r<x)return;
		if(x<=l&&r<=y)return lz[i]=v,pushlz(l,r,i),void();
		int m=(l+r)/2;
		update(l,m,i*2,x,y,v);
		update(m+1,r,i*2+1,x,y,v);
		t[i]=t[i*2]+t[i*2+1];
	}
	void update(int x,int y,int v){
		update(1,n,1,x,y,v);
	}
	int query(int l,int r,int i,int x){
		pushlz(l,r,i);
		if(l==r)return t[i].val;
		int m=(l+r)/2;
		if(x<=m)return query(l,m,i*2,x);
		return query(m+1,r,i*2+1,x);
	}
	int query(int x){
		return query(1,n,1,x);
	}
}s;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
	h=H,w=W;
	n=h*w;
	val[0]=val[n+1]=inf;
	for(int i=1;i<=n;i++){
		r[i]=R[i-1]+1;
		c[i]=C[i-1]+1;
		val[c[i]]=i;
	}
	for(int i=1;i<=n;i++){
		pref[i]=pref[i-1]+calc(c[i]);
	}
	s.build();
}

int swap_seats(int a, int b){
	a++,b++;
	if(c[a]>c[b])swap(a,b);
	if(c[b]-c[a]>2){
		for(int i=-1;i<=1;i++){
			s.update(val[c[a]+i],n,-calc(c[a]+i));
			s.update(val[c[b]+i],n,-calc(c[b]+i));
		}
		swap(r[a],r[b]);
		swap(c[a],c[b]);
		val[c[a]]=a;
		val[c[b]]=b;
		for(int i=-1;i<=1;i++){
			s.update(val[c[a]+i],n,calc(c[a]+i));
			s.update(val[c[b]+i],n,calc(c[b]+i));
		}
	}else{
		for(int i=c[a]-1;i<=c[b]+1;i++){
			s.update(val[i],n,-calc(i));
		}
		swap(r[a],r[b]);
		swap(c[a],c[b]);
		val[c[a]]=a;
		val[c[b]]=b;
		for(int i=c[b]-1;i<=c[a]+1;i++){
			s.update(val[i],n,calc(i));
		}
	}
	for(int i=1;i<=n;i++){
		pref[i]=pref[i-1]+calc(c[i]);
	}
	int idx=1,ans=0;
	return s.t[1].freq;
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:124:6: warning: unused variable 'idx' [-Wunused-variable]
  124 |  int idx=1,ans=0;
      |      ^~~
seats.cpp:124:12: warning: unused variable 'ans' [-Wunused-variable]
  124 |  int idx=1,ans=0;
      |            ^~~

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