Submission #738258

#	Time	Username	Problem	Language	Result	Execution time	Memory
738258		myrcella	Seats (IOI18_seats)	C++17	100 / 100	3146 ms	93704 KiB

seats

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "seats.h"

const int maxn = 3e6+10;
pair<pii,int> tree[maxn*4];
pii add[maxn*4];
int n;
int val[maxn];
pii pos[maxn];
int h,w;

void update(int c,int cl,int cr,int l,int r,int val1,int val2) {
	if (l<=cl and cr<=r) {
		tree[c].fi.fi += val1;
		tree[c].fi.se += val2;
		add[c].fi += val1;
		add[c].se += val2;
		return;
	}
	if (add[c]!=MP(0,0)) {
		tree[c<<1].fi.fi += add[c].fi;
		tree[c<<1].fi.se += add[c].se;
		add[c<<1].fi += add[c].fi;
		add[c<<1].se += add[c].se;
		
		tree[c<<1|1].fi.fi += add[c].fi;
		tree[c<<1|1].fi.se += add[c].se;
		add[c<<1|1].fi += add[c].fi;
		add[c<<1|1].se += add[c].se;
		
		add[c] = {0,0};
	}
	int mid=cl+cr>>1;
	if (l<=mid) update(c<<1,cl,mid,l,r,val1,val2);
	if (r>mid) update(c<<1|1,mid+1,cr,l,r,val1,val2);
	if (tree[c<<1].fi==tree[c<<1|1].fi) tree[c] = {tree[c<<1].fi,tree[c<<1].se+tree[c<<1|1].se};
	else tree[c] = min(tree[c<<1],tree[c<<1|1]);
}

void update(int x,int y,int v) {
	int tm[4] = {val[x*w+y],val[x*w+y+1],val[(x+1)*w+y],val[(x+1)*w+y+1]};
	sort(tm,tm+4);
	if (tm[0]<tm[1]) update(1,0,n-1,tm[0],tm[1]-1,v,0);
	if (tm[2]<tm[3]) update(1,0,n-1,tm[2],tm[3]-1,0,v);
}

void init(int c,int cl,int cr) {
	tree[c] = {{0,0},cr-cl+1};
	add[c] = {0,0};
	if (cl==cr) return;
	int mid=cl+cr>>1;
	init(c<<1,cl,mid);
	init(c<<1|1,mid+1,cr);
	return;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  n = H*W;
  h = H+2,w=W+2;
  rep(i,0,maxn) val[i] = n;
  rep(i,0,n) {
	  R[i]++;
	  C[i]++;
	  val[R[i]*w+C[i]] = i;
	  pos[i] = {R[i],C[i]};
  }
  init(1,0,n-1);
  rep(i,0,h-1)
	rep(j,0,w-1) 
		update(i,j,1);
}

int swap_seats(int a, int b) {
	update(pos[a].fi,pos[a].se,-1);update(pos[a].fi-1,pos[a].se,-1);update(pos[a].fi,pos[a].se-1,-1);update(pos[a].fi-1,pos[a].se-1,-1);
	update(pos[b].fi,pos[b].se,-1);update(pos[b].fi-1,pos[b].se,-1);update(pos[b].fi,pos[b].se-1,-1);update(pos[b].fi-1,pos[b].se-1,-1);
	swap(pos[a],pos[b]);
	swap(val[pos[a].fi*w+pos[a].se],val[pos[b].fi*w+pos[b].se]);
	update(pos[a].fi,pos[a].se, 1);update(pos[a].fi-1,pos[a].se, 1);update(pos[a].fi,pos[a].se-1, 1);update(pos[a].fi-1,pos[a].se-1, 1);
	update(pos[b].fi,pos[b].se, 1);update(pos[b].fi-1,pos[b].se, 1);update(pos[b].fi,pos[b].se-1, 1);update(pos[b].fi-1,pos[b].se-1, 1);
	assert(tree[1].fi==MP(4,0));
	return tree[1].se;
}

Compilation message (stderr)

seats.cpp: In function 'void update(int, int, int, int, int, int, int)':
seats.cpp:55:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |  int mid=cl+cr>>1;
      |          ~~^~~
seats.cpp: In function 'void init(int, int, int)':
seats.cpp:73:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |  int mid=cl+cr>>1;
      |          ~~^~~

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