Submission #139279

#	Time	Username	Problem	Language	Result	Execution time	Memory
139279		rajarshi_basu	Seats (IOI18_seats)	C++14	0 / 100	3782 ms	57080 KiB

seats

#include <bits/stdc++.h>

#include "seats.h"

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ii pair<int,int>
#define il pair<int,ll>
#define vv vector	

using namespace std;

const int MAXN = 1000*1000+5;


struct Segtree{
	int st[4*MAXN];
	void update(int node,int ss,int se,int i,int val){
		if(i > se or i < ss)return;
		if(ss == se){
			st[node] = val;
			return;
		}
		int mid = (ss+se)/2;
		update(node*2+1,ss,mid,i,val);
		update(node*2+2,mid+1,se,i,val);
		st[node] = max(st[node*2+1],st[node*2+2]);
	}
	// returns the first element greater or equal to the specified element;
	int getFirst(int node,int ss,int se,int val){
		if(st[node] < val)return -2;
		if(ss == se){return st[node] == val?ss:-1;}
		int mid = (ss+se)/2;
		int vv = getFirst(node*2+1,ss,mid,val);
		if(vv <= -2)return getFirst(node*2+2,mid+1,se,val);
		return vv;
	}
};

ii id[MAXN];
int h;
int w;

Segtree lft,rght,up,down;
struct Event{
	int tm;
	int id; // 0 is lft,1 is rght,2 is up,3 is down;
	int val;
	Event(int a,int b,int c){
		tm = a+1;
		id = b;
		val = c;
	}
};

int update(int a,int b,bool bb = 1){
	
	if(bb){swap(id[a],id[b]);
	
		up.update(0,0,h*w-1,a,-id[a].ff);
		up.update(0,0,h*w-1,b,-id[b].ff);
	
		down.update(0,0,h*w-1,a,id[a].ff);
		down.update(0,0,h*w-1,b,id[b].ff);
	
		lft.update(0,0,w*h-1,a,-id[a].ss);
		lft.update(0,0,w*h-1,b,-id[b].ss);
	
		rght.update(0,0,w*h-1,a,id[a].ss);
		rght.update(0,0,w*h-1,b,id[b].ss);
	}
	
	vv<Event> events;
	FOR(i,h){
		int tm = up.getFirst(0,0,w*h-1,-i);
		if(tm <= -1)continue;
		events.pb(Event(tm,2,i));
	}
	FOR(i,h){
		int tm = down.getFirst(0,0,w*h-1,i);
		if(tm <= -1)continue;
		events.pb(Event(tm,3,i));
	}
	FOR(i,w){
		int tm = lft.getFirst(0,0,w*h-1,-i);
		if(tm <= -1)continue;
		events.pb(Event(tm,0,i));
	}
	FOR(i,w){
		int tm = rght.getFirst(0,0,w*h-1,i);
		if(tm <= -1)continue;
		events.pb(Event(tm,1,i));
	}
	// all events have been generated;
	for(auto e : events){
	//	cout << e.tm << " " << e.id << " " << e.val << endl;
	}
	sort(events.begin(),events.end(),[&](Event a,Event b){
		return a.tm < b.tm;
	});
	for(auto e : events){
	//	cout << e.tm << " " << e.id << " " << e.val << endl;
	}
	
	int parea = 1;
	int lstTm = 1;
	int area = 1;
	int cnt = 1;
	int l = id[0].ss,r = id[0].ss,u = id[0].ff,d = id[0].ff;
	bool lst = 0;
	for(auto e : events){
		if(e.tm <= 1)continue;
		
	
		if(e.id == 0){
			l = min(e.val,l);
		}else if(e.id == 1){
			r = max(e.val,r);
		}else if(e.id == 2){
			u = min(u,e.val);
		}else{
			d = max(d,e.val);
		}
		area = (r-l+1)*(d-u+1);
		int ntm = e.tm;
		//cout << l << " " << r << " " << u << " " << d << endl;
		//cout << cnt << endl;
		if(area == ntm){
		//	cout << "oof" << endl;
			cnt++;
		}
		if(lstTm+1 < ntm){
			
			ll v1 = parea - lstTm +1;
			ll v2 = parea - ntm -1;
			if(v1*v2 <= 0)cnt++;
				
		}
		if(area == h*w and ntm != h*w)lst = 1;	
		parea = area;
		lstTm = ntm;
	}
	if(lstTm != h*w)cnt++;
	return cnt;
}

void give_initial_chart(int h,int w,vi r,vi c){
	::h = h;::w = w;
	
	FOR(i,h*w){
		id[i] = {r[i],c[i]};
		up.update(0,0,h*w-1,i,-id[i].ff);
		down.update(0,0,w*h-1,i,id[i].ff);
		lft.update(0,0,w*h-1,i,-id[i].ss);
		rght.update(0,0,w*h-1,i,id[i].ss);
	}
	
	
	//cout << update(0,0,0) << endl;
	//FOR(i,h*w)ok[i] = 0;
	//update(0,h*w-1,0);
	//FOR(i,h*w)cout << ok[i];cout << endl;
	//FOR(i,h*w)cout << l[i] << " " << r[i] << " " << u[i] << " " << d[i] << endl;
}

int swap_seats(int a,int b){
	return update(min(a,b),max(a,b));
	//return cnt;
}

Compilation message (stderr)

seats.cpp: In function 'int update(int, int, bool)':
seats.cpp:100:11: warning: variable 'e' set but not used [-Wunused-but-set-variable]
  for(auto e : events){
           ^
seats.cpp:106:11: warning: variable 'e' set but not used [-Wunused-but-set-variable]
  for(auto e : events){
           ^
seats.cpp:115:7: warning: variable 'lst' set but not used [-Wunused-but-set-variable]
  bool lst = 0;
       ^~~

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