Submission #131556

#	Time	Username	Problem	Language	Result	Execution time	Memory
131556		rondojim	Seats (IOI18_seats)	C++17	37 / 100	4058 ms	123676 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
vector<vector<int>> mp;
int seg[5][4000005],lazy[4000005],N;
pii pl[1000005];
 
void modify(int L,int R,int l,int r,int rt,int v)
{
	if(L<=l&&R>=r)
		return lazy[rt]+=v,void();
	int m=l+r>>1;
	if(L<=m) modify(L,R,l,m,rt<<1,v);
	if(R>m) modify(L,R,m+1,r,rt<<1|1,v);
	for(int i=0;i<5;++i)
	{
		seg[i][rt]=0;
		if(lazy[rt<<1]>i)
			seg[i][rt]+=m-l+1;
		else
			seg[i][rt]+=seg[i-lazy[rt<<1]][rt<<1];
		if(lazy[rt<<1|1]>i)
			seg[i][rt]+=r-m;
		else
			seg[i][rt]+=seg[i-lazy[rt<<1|1]][rt<<1|1];
	}
}
 
void range(int l,int r,int v)
{
	if(l<r)
		modify(l,r-1,0,N,1,v);
}
 
void segment(int x,int y,int v)
{
	vector<int> tmp{mp[x][y],mp[x+1][y],mp[x][y+1],mp[x+1][y+1]};
	sort(ALL(tmp));
	range(tmp[0],tmp[1],v),range(tmp[2],tmp[3],v);
}
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	N=H*W;
	mp.resize(H+2,vector<int>(W+2,N));
	for(int i=0;i<N;++i)
		mp[R[i]+1][C[i]+1]=i,pl[i]=MP(R[i]+1,C[i]+1);
	for(int i=0;i<=H;++i)
		for(int j=0;j<=W;++j)
			segment(i,j,1);
}
 
int swap_seats(int a, int b)
{
	segment(pl[a].F-1,pl[a].S-1,-1),segment(pl[a].F,pl[a].S-1,-1),segment(pl[a].F-1,pl[a].S,-1),segment(pl[a].F,pl[a].S,-1);
	mp[pl[a].F][pl[a].S]=b;
	segment(pl[a].F-1,pl[a].S-1,1),segment(pl[a].F,pl[a].S-1,1),segment(pl[a].F-1,pl[a].S,1),segment(pl[a].F,pl[a].S,1);
	segment(pl[b].F-1,pl[b].S-1,-1),segment(pl[b].F,pl[b].S-1,-1),segment(pl[b].F-1,pl[b].S,-1),segment(pl[b].F,pl[b].S,-1);
	mp[pl[b].F][pl[b].S]=a;
	segment(pl[b].F-1,pl[b].S-1,1),segment(pl[b].F,pl[b].S-1,1),segment(pl[b].F-1,pl[b].S,1),segment(pl[b].F,pl[b].S,1);
	swap(pl[a],pl[b]);
	return seg[3][1]-seg[4][1];
}

Compilation message (stderr)

seats.cpp: In function 'void modify(int, int, int, int, int, int)':
seats.cpp:25:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~

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