Submission #127192

#	Time	Username	Problem	Language	Result	Execution time	Memory
127192		baluteshih	Port Facility (JOI17_port_facility)	C++14	0 / 100	45 ms	47352 KiB

port_facility

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define ET cout << "\n"
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll MOD=1e9+7;
vector<int> G[1000005];
vector<pii> st;
list<int> ls[1000005];
pii seg[1000005];

int main()
{jizz
	int n,flag=1,ans=1,tp=0;
	cin >> n;
	for(int i=0;i<n;++i)
		cin >> seg[i].F >> seg[i].S;
	sort(seg,seg+n);
	for(int i=0;i<n&&flag;++i)
	{
		while(!st.empty()&&ls[st.back().F].front()<seg[i].F)
		{
			ls[st.back().F].erase(ls[st.back().F].begin());
			if(ls[st.back().F].empty())
			{
				if(!st.back().S) ans=ans*2%MOD;
				st.pop_back();
			}
		}
		int beg=-1,tg=0;
		while(!st.empty()&&ls[st.back().F].front()<seg[i].S)
		{
			if(tg)
			{
				flag=0;
				break;
			}
			if(!~beg) beg=st.back().F;
			else ls[beg].splice(ls[beg].end(),ls[st.back().F]);
			if(st.back().S) tg=1;
			st.pop_back();
		}
		if(~beg&&ls[beg].back()>seg[i].S)
			flag=0;
		if(!flag) break;
		if(tg)
			ls[st.back().F].insert(ls[st.back().F].begin(),seg[i].S);
		else
			st.pb(MP(++tp,0)),ls[tp].pb(seg[i].S);
		if(~beg)
			st.pb(MP(beg,1));
		//cout << i << ":\n";
		//for(int i=0;i<st.size();++i)
		//{
		//	cout << "{";
		//	for(auto j:ls[st[i].F])
		//		cout << j << ",";
		//	cout << "} ";
		//}
		//ET;
	}
	for(;!st.empty();st.pop_back())
		if(!st.back().S)
			ans=ans*2%MOD;
	if(flag) cout << ans << "\n";
	else cout << "0\n";
}

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