Submission #465035

#	Time	Username	Problem	Language	Result	Execution time	Memory
465035		architkarandikar	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	204 KiB

port_facility

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <limits>
#include <string>
#include <cassert>

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define forup(i,a,b) for(int i=a; i<b; ++i)
#define fordn(i,a,b) for(int i=a; i>b; --i)
#define rep(i,a) for(int i=0; i<a; ++i)

#define dforup(i,a,b) for(i=a; i<b; ++i)
#define dfordn(i,a,b) for(i=a; i>b; --i)
#define drep(i,a) for(i=0; i<a; ++i)

#define slenn(s,n) for(n=0; s[n]!=13 and s[n]!=0; ++n);s[n]=0

#define gi(x) scanf("%d",&x)
#define gl(x) cin>>x
#define gd(x) scanf("%lf",&x)
#define gs(x) scanf("%s",x)

#define pis(x) printf("%d ",x)
#define pin(x) printf("%d\n",x)
#define pls(x) cout<<x<<" "
#define pln(x) cout<<x<<"\n"
#define pds(x) printf("%.12f ",x)
#define pdn(x) printf("%.12f\n",x)
#define pnl() printf("\n")

#define fs first
#define sc second

#define pb push_back

const int inv=1000000000;
const int minv=-inv;

// BIT struct

struct BIT
{
	int bn; //bn>0
	vector<int> bA;
	
	BIT(){ bn=0; }
	BIT(int bn_){ bn=bn_; bA.resize(bn+1); fill(bA.begin(),bA.end(),0); }
	
	int prefix(int bposn)
	{
		if(bposn<=0) return 0;
		if(bposn>bn) bposn=bn;
		
		int ret=0;
		for(int i=bposn; i>0; i-=((i)&(-i)))
			ret+=bA[i];
		return ret;
	}
	
	void update(int bposn, int bincr)
	{
		if(bposn<=0) return;
		if(bposn>bn) return;
		
		for(int i=bposn; i<=bn; i+=((i)&(-i)))
			bA[i]+=bincr;
	}
	
	int query(int bl, int br)
	{
		if(bl>br) return 0;
		return (prefix(br)-prefix(bl-1));
	}
};

// End of BIT struct

const int max_n=1000000+5;
const int modref=((int)(1e9))+7;

int n;
pii e[2*max_n+1];
int d[2*max_n+1];

int r[max_n];
int res;

stack<int> S;
BIT bit[2];

int main()
{
	gi(n);

	int a,b;
	rep(i,n)
	{
		gi(a); gi(b);
		e[a]=pii(0,i);
		e[b]=pii(1,i);
		d[b]=a;
	}

	res=1;
	fill(r,r+n,-1);
	rep(k,2)
		bit[k]=BIT(2*n);
	forup(j,1,2*n+1)
	{
		int t=e[j].fs;
		int i=e[j].sc;

		if(t==0)
		{
			S.push(j);
			continue;
		}

		if(r[i]!=-1)
		{
			if(bit[r[i]].query(d[j]+1,j-1)>0)
			{
				res=0;
				continue;
			}
			bit[r[i]].update(j,-1);
		}
		else
		{
			int open=0;
			int openk;
			rep(k,2)
				if(bit[k].query(d[j]+1,j-1)==0)
				{
					++open;
					openk=k;
				}

			if(open==0)
			{
				res=0;
				continue;
			}
			else if(open==2)
			{
				res*=2;
				res%=modref;
			}
			r[i]=openk;
		}

		while((not S.empty()) and S.top()>=d[j])
		{
			if(S.top()!=d[j])
			{
				r[e[S.top()].sc]=1-r[i];
				bit[1-r[i]].update(S.top(),1);
			}
			S.pop();
		}
	}

	pin(res);
	
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:38:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 | #define gi(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
port_facility.cpp:113:2: note: in expansion of macro 'gi'
  113 |  gi(n);
      |  ^~
port_facility.cpp:38:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 | #define gi(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
port_facility.cpp:118:3: note: in expansion of macro 'gi'
  118 |   gi(a); gi(b);
      |   ^~
port_facility.cpp:38:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 | #define gi(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
port_facility.cpp:118:10: note: in expansion of macro 'gi'
  118 |   gi(a); gi(b);
      |          ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22