Submission #1034463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034463		vjudge1	Seats (IOI18_seats)	C++17	5 / 100	4099 ms	64340 KiB

seats

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

#define fst first 
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n';
#define pi pair<int,int>
#define pll pair<ll,ll>
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;

#include "seats.h"

ll n,m;
vector<vector<ll>> trix;
vector<vector<bool>> visited;
vector<vector<bool>> actived;
pair< pair<ll,ll> , pair<ll,ll> > initRange;

vector<ll> r;
vector<ll> c;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	n = H; 
	m = W;
	
	r.resize(SZ(R));
	c.resize(SZ(C));
	trix.resize(n,vector<ll>(m));

	forn(i,0,SZ(R)){
		r[i]=R[i];
		c[i]=C[i];
		trix[R[i]][C[i]]=i;
	}
	
	initRange={ {R[0],C[0]} , {R[0],C[0]} };
}

ll walk(pair< pair<ll,ll> , pair<ll,ll> > lrange, pair< pair<ll,ll> , pair<ll,ll> > range){
	ll res = 0;
	for(int i = range.fst.fst; i <= range.snd.fst; i++){ 
		if(i<lrange.fst.fst||i>lrange.snd.fst){
			for(int j = range.fst.snd; j <= range.snd.snd; j++){
				//cout<<trix[i][j]<<'\n';
				res=max(res,trix[i][j]);
			}
		}else{
			for(int j = range.fst.snd; j < lrange.fst.snd; j++){
				//cout<<trix[i][j]<<'\n';
				res=max(res,trix[i][j]);
			}
			for(int j = lrange.snd.snd+1; j <= range.snd.snd; j++){
				//cout<<trix[i][j]<<'\n';
				res=max(res,trix[i][j]);
			}
		}
	}
	return res;
}

int swap_seats(int a, int b) {
	
	trix[r[a]][c[a]]=b;
	trix[r[b]][c[b]]=a;
	
	ll row = r[a];
	ll col = c[a];
	
	r[a]=r[b];
	c[a]=c[b];
	r[b]=row;
	c[b]=col;

	pair< pair<ll,ll> , pair<ll,ll> > lrange; // last range
	pair< pair<ll,ll> , pair<ll,ll> > range; // actual range
	lrange={ {r[0],c[0]} , {r[0],c[0]} };
	ll res = 1;
	ll maxi = 0;
	for(int i = 1; i < SZ(r); i++){
		//cout<<"I: "<<i<<'\n';
		range = lrange;
		range.fst.fst = min( range.fst.fst , r[i]);
		range.fst.snd = min( range.fst.snd , c[i]);
		
		range.snd.fst = max( range.snd.fst , r[i]);
		range.snd.snd = max( range.snd.snd , c[i]);
		
		/*cout<<range.fst.fst<<" "<<range.fst.snd<<" | "<<range.snd.fst<<" "<<range.snd.snd<<'\n';
		cout<<lrange.fst.fst<<" "<<lrange.fst.snd<<" | "<<lrange.snd.fst<<" "<<lrange.snd.snd<<'\n';*/
		bool operar = false;
		if(range.fst.fst!=lrange.fst.fst || range.fst.snd!=lrange.fst.snd || range.snd.fst!=lrange.snd.fst || range.snd.snd!=lrange.snd.snd) operar = true;
		if(operar) maxi=max(maxi,walk(lrange,range));
		if( operar && maxi < (range.snd.fst-range.fst.fst+1)*(range.snd.snd-range.fst.snd+1)) res++;
		
		lrange=range;
	}
	return res;		
}

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