LA 3525

From Algorithmist
Jump to navigation Jump to search

LA 3525 - Wild West[edit]


There are gunmen characterized by three different skills, each ranging from 1 to M. A subset containing N of these gunmen are The Bad Guys. We want to select one of the other gunmen to be a Hero. The Hero must beat each of the Bad Guys in at least one skill (not necessarily the same skill for all Bad Guys).

The task is to compute the number of gunmen that can be selected to be the Hero.


Instead of calculating directly the number of gunmen who can be Heroes, one can calculate the number of gunmen who can't be heroes, and subtract this from to get the final answer. Consider a Bad Guy with skills [a,b,c]. The set of gunmen that can't beat him is a cuboid with opposite corners [1,1,1] and [a,b,c]. Alternatively, consider the Bad Guy to be the point (a,b,c). The number of gunmen who can't defeat him is the volume of the cuboid defined by the opposite vertices (0,0,0) and (a,b,c). When all Bad Guys are considered, the total number of gunmen who can't be Heroes is the volume of the union of all cuboids thus formed (one for each Bad Guy.)

The tricky part is computing the volume of this union. The easiest way to do this is to divide the union into "slices" along one of the three dimensions (skills). The volume of each slice is equal to its thickness multiplied by the area of its cross-section. This area can be updated in (log ) time using a balanced binary search tree as we sweep through the set of Bad Guys.


In C++, STL sets can be used, there is no need to implement the tree-like structure.

--- my code accepted at archive --
// code of myprasanna
using namespace std;
#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <string>

#define V(x) vector< x >
#define LET(x,a) __typeof(a) x(a)
#define FOR(i,a,b) for(LET(i,(a));i!=(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(it,v) FOR(it,(v).begin(),(v).end())
#define ALL(f,x) ({ bool _ok = true ; f if( ! (x) ) { _ok=false; break; } ; _ok; })
#define EXISTS(f,x) ({ book _ok=false; f if( x ) { _ok=true;break;} ; _ok; })
#define COUNT(f,x) ({int _cnt=0; f if (x) ++_cnt; _cnt; })
#define sz size()
#define cs c_str()
#define pb push_back
#define GI ({int t;scanf("%d",&t); t;})
#define INF (int)1e9
#define MIN(f,x) ({int k=INF;f k<?=(x);k;})
#define MAX(f,x) ({int k=0;f k>?=(x);k;})
#define isi(s) ({int i;sscanf((s).CS,"%d",&i)==1;})
#define s2i(s) (atoi((s).CS))
#define dbg(x) cout << #x << " -> " << (x) << "\t";
#define dbge(x) cout << #x << " -> " << (x) << endl;

typedef V(int) VI;
typedef V(string) VS;
typedef V(VI) VII;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
#define MN ((int)1e5+10)
LL n, m;
LL ans, area;
map<int,int> Ht;

void ins(int x, int y) {
	while(1) {
		LET(it, Ht.lower_bound(x));
		int cy = it->second;
		if(it == Ht.begin()) break;
		if(it->second > y) break;
		int a = it->first, b = it->second;
		assert(it != Ht.begin());
			a -= it->first ; assert(a >= 0);
			b -= cy; assert( b >= 0);
			++ it;
		//dbg(it->first); dbge(it->second);
		assert( a * b >= 0);
		area -= a* LL(b);
		LET(it, Ht.lower_bound(x));
		if(it->second >= y) return;
		int na = it->first, nb = it->second;
		assert(it != Ht.begin());
		assert((x - it->first) * LL(y - nb) >= 0);
		area += (x - it->first) * LL(y - nb);
		Ht[x] = y;

int main() {
	while( n = GI ) {
		m = GI; ans = area = 0; Ht.clear(); Ht[0] = 1+m; Ht[m] = 0;
		REP(i,n) P[i].first = GI, P[i].second.first = GI, P[i].second.second = GI;
		int pp = 0;
		for(int fir = m; fir >= 1; fir--) { // first co-ordinate goes in decreasing order.
			while( pp < n && fir == P[pp].first ) {
				ins(P[pp].second.first, P[pp].second.second);
				pp ++;
			ans += (m*m - area);
			assert( area <= m*m );
			//dbg(fir); dbg(area); dbge(m*m - area);
		cout << ans << endl;
	return 0;


3 10
2 8 5
6 3 5
1 3 9
1 3
2 2 2
1 10000
2 2 2
0 0