Submission #349283

#	Time	Username	Problem	Language	Result	Execution time	Memory
349283		Kerim	Seats (IOI18_seats)	C++17	33 / 100	837 ms	73452 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;
int h,w,val[MAXN],delta[MAXN];
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=w-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 x){
	if(x<0 or x>=w)return;
	delta[x]=0;
	if(val[c[x]-1]>x)delta[x]++;
	else delta[x]--;
	if(val[c[x]+1]>x)delta[x]++;
	else delta[x]--;
	upd(x,delta[x]);
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C) {
  	r=R;c=C;h=H;w=W;assert(h==1);
  	val[0]=val[w+1]=w;
  	for(int i=0;i<w;i++)
 		val[++c[i]]=i;
  	for(int i=0;i<w;i++)add(i);
}

int swap_seats(int a, int b) {
	swap(val[c[a]],val[c[b]]);
	swap(c[a],c[b]);
	for(int i=-1;i<=1;i++)
		add(val[c[a]+i]),add(val[c[b]+i]);
	assert(s[1].mn==2);
	return s[1].cnt;
}

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