UVA 12356 : Army Buddies

Link : UVA12356

Category : Data Structure

Solution : Simple segment tree data structure suffices. Each node of the tree has a boolean variable indicating if at all it is possible to find an alive soldier in this range of soldiers.

Code:

	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <queue>
	#include <stack>
	#include <map>
	#include <set>
	#include <utility>
	#include <climits>
	#include <cfloat>
	#include <cassert>
	using namespace std;
	#define read(n) scanf("%d",&n)
	#define read2(n,m) scanf("%d%d",&n,&m)
	#define read3(n,m,l) scanf("%d%d%d",&n,&m,&l)
	#define readull(n) scanf("%llu",&n)
	#define readll(n) scanf("%lld",&n)
	#define ull unsigned long long int
	#define ll long long int
	#define vi vector<int>
	#define vs vector<string>
	bool *mem;
	void init(int l,int h,int pos){
	if(l==h) mem[pos]=true;
	else{
	mem[pos]=true;
	init(l,(l+h)/2,2*pos);
	init(1+(l+h)/2,h,2*pos+1);
	}
	}
	void remove(int l,int h,int pos,int x,int y){
	if(y<l or x>h) return;
	if(l>=x and h<=y){
	mem[pos]=false;
	return;
	}
	remove(l,(l+h)/2,2*pos,x,y);
	remove(1+(l+h)/2,h,2*pos+1,x,y);
	mem[pos]=mem[2*pos] or mem[1+2*pos];
	}
	int get(int l,int h,int pos,int x,int y){
	if(y<x) return -1;
	if(y<l or x>h) return -1;
	if(mem[pos]==0) return -1;
	if(l==h) return l;
	int ret=get(1+(l+h)/2,h,2*pos+1,x,y);
	if(ret==-1) ret=get(l,(l+h)/2,2*pos,x,y);
	return ret;
	}
	int get1(int l,int h,int pos,int x,int y){
	if(y<x) return -1;
	if(y<l or x>h) return -1;
	if(mem[pos]==0) return -1;
	if(l==h) return l;
	int ret=get1(l,(l+h)/2,2*pos,x,y);
	if(ret==-1) ret=get1(1+(l+h)/2,h,2*pos+1,x,y);
	return ret;
	}
	int main(){
	mem=new bool[1000000];
	int s,b,x,y;
	while(1){
	read2(s,b);
	if(b==0 and s==0) return 0;
	init(1,s,1);
	while(b--){
	read2(x,y);
	remove(1,s,1,x,y);
	int left=get(1,s,1,1,x-1);
	int rght=get1(1,s,1,y+1,s);
	if(left==-1) printf("* ");
	else printf("%d ",left);
	if(rght==-1) printf("*\n");
	else printf("%d\n",rght);
	}
	printf("-\n");
	}
	return 0;
	}

view raw UVA12356.cpp hosted with ❤ by GitHub