Submission #111172

#	Time	Username	Problem	Language	Result	Execution time	Memory
111172		kig9981	Seats (IOI18_seats)	C++17	0 / 100	1262 ms	60256 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
 
using namespace std;
 
const int SZ=1<<20, dx[]={-1,0,1,0}, dy[]={0,-1,0,1};
vector<pair<int,int>> P;
pair<int,int> tree[2*SZ], lazy[2*SZ];
int N, M, tcnt[2*SZ], idx[1000000];
 
void lazy_propagation(int bit, int s, int e)
{
	tree[bit].first+=lazy[bit].first;
	tree[bit].second+=lazy[bit].second;
	if(s<e) {
		lazy[2*bit].first+=lazy[bit].first;
		lazy[2*bit].second+=lazy[bit].second;
		lazy[2*bit+1].first+=lazy[bit].first;
		lazy[2*bit+1].second+=lazy[bit].second;
	}
	lazy[bit]={0,0};
}
 
void add_tree(int n1, int n2, pair<int,int> v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		tree[bit].first+=v.first;
		tree[bit].second+=v.second;
		if(s<e) {
			lazy[2*bit].first+=v.first;
			lazy[2*bit].second+=v.second;
			lazy[2*bit+1].first+=v.first;
			lazy[2*bit+1].second+=v.second;
		}
		return;
	}
	add_tree(n1,n2,v,2*bit,s,m);
	add_tree(n1,n2,v,2*bit+1,m+1,e);
	tree[bit]=min(tree[2*bit],tree[2*bit+1]);
	tcnt[bit]=(tree[bit]==tree[2*bit] ? tcnt[2*bit]:0)+(tree[bit]==tree[2*bit+1] ? tcnt[2*bit+1]:0);
}
 
bool valid_coord(int x, int y)
{
	return 0<=x && x<N && 0<=y && y<M;
}
 
int &convert(int x, int y)
{
	return idx[x*M+y];
}
 
pair<int,int> get_corner(int x, int y, int i)
{
	pair<int,int> ret;
	for(int k=0;k<4;k++) {
		if(valid_coord(x+dx[k],y+dy[k]) && valid_coord(x+dx[(k+1)&3],y+dy[(k+1)&3]) && convert(x+dx[k],y+dy[k])<=i && convert(x+dx[(k+1)&3],y+dy[(k+1)&3])<=i && convert(x,y)>i) {
			ret.second++;
		}
		else if((!valid_coord(x+dx[k],y+dy[k]) || convert(x+dx[k],y+dy[k])>i) && (!valid_coord(x+dx[(k+1)&3],y+dy[(k+1)&3]) || convert(x+dx[(k+1)&3],y+dy[(k+1)&3])>i) && convert(x,y)<=i) {
			ret.first++;
		}
	}
	return ret;
}
 
pair<int,int> get_diff(int i)
{
	pair<int,int> ret, temp;
	int x=P[i].first, y=P[i].second;
	temp=get_corner(x,y,i); ret.first+=temp.first; ret.second+=temp.second;
	temp=get_corner(x,y,i-1); ret.first-=temp.first; ret.second-=temp.second;
	for(int k=0;k<4;k++) if(valid_coord(x+dx[k],y+dy[k])) {
		temp=get_corner(x+dx[k],y+dy[k],i); ret.first+=temp.first; ret.second+=temp.second;
		temp=get_corner(x+dx[k],y+dy[k],i-1); ret.first-=temp.first; ret.second-=temp.second;
	}
	return ret;
}
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	P.resize(H*W);
	N=H; M=W;
	for(int i=0;i<H*W;i++) {
		P[i]={R[i],C[i]};
		convert(R[i],C[i])=i;
		tcnt[SZ+i]=1;
	}
	tree[SZ]=get_diff(0);
	for(int i=1;i<H*W;i++) {
		tree[SZ+i]=get_diff(i);
		tree[SZ+i].first+=tree[SZ+i-1].first;
		tree[SZ+i].second+=tree[SZ+i-1].second;
	}
	for(int i=H*W;i<SZ;i++) tree[SZ+i]=make_pair(0x1fffffff,0x1fffffff);
	for(int i=SZ-1;i;i--) {
		tree[i]=min(tree[2*i],tree[2*i+1]);
		tcnt[i]=(tree[i]==tree[2*i] ? tcnt[2*i]:0)+(tree[i]==tree[2*i+1] ? tcnt[2*i+1]:0);
	}
}
 
int swap_seats(int a, int b)
{
	pair<int,int> temp;
	int x1=P[a].first, y1=P[a].second, x2=P[b].first, y2=P[b].second;
	vector<int> C;
	C.push_back(a);
	C.push_back(b);
	for(int k=0;k<4;k++) {
		if(valid_coord(x1+dx[k],y1+dy[k])) C.push_back(convert(x1+dx[k],y1+dy[k]));
		if(valid_coord(x2+dx[k],y2+dy[k])) C.push_back(convert(x2+dx[k],y2+dy[k]));
	}
    C.push_back(SZ-1);
  	sort(C.begin(),C.end());
  	C.resize(unique(C.begin(),C.end())-C.begin());
	for(int i=0;i<C.size()-1;i++) {
		temp=get_diff(C[i]); temp.first*=-1; temp.second*=-1;
		add_tree(C[i],C[i+1],temp);
	}
	swap(P[a],P[b]);
	swap(convert(P[a].first,P[a].second),convert(P[b].first,P[b].second));
	for(int i=0;i<C.size()-1;i++) add_tree(C[i],C[i+1],get_diff(C[i]));
	return tcnt[1];
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:119:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<C.size()-1;i++) {
              ~^~~~~~~~~~~
seats.cpp:125:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<C.size()-1;i++) add_tree(C[i],C[i+1],get_diff(C[i]));
              ~^~~~~~~~~~~

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