Submission #20492

#	Time	Username	Problem	Language	Result	Execution time	Memory
20492		볼빨간민돌이 (#35)	초음속철도 (OJUZ11_rail)	C++11	18 / 100	446 ms	7868 KiB

rail

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

const int MAXM = 200000;
const int mod = 1e9+7;
int n, m, s[MAXM+1], e[MAXM+1];

int myPow(int a, int r){
	if(r==0) return 1;
	int half=myPow(a, r/2);
	if(r&1) return half*1ll*half%mod*a%mod;
	else return half*1ll*half%mod;
}

bool use[MAXM+1];
int check(){
	vector<pair<int, int>> v;

    for(int i=1; i<=m; i++)
		if(use[i]) v.push_back(make_pair(s[i], e[i]));
    sort(v.begin(), v.end());
    if(v.empty()) return 0;

    int now=1;
    for(auto &e:v){
		if(e.first > now) break;
		else now=max(now, e.second);
    }
    return now==n;
}

int f(int now){
	if(now==m+1) return check();

	int sum=0;
	use[now]=true;
	sum+=f(now+1);
	use[now]=false;
	sum+=f(now+1);
	return sum;
}

bool comp3(const pair<int, int> &p1, const pair<int, int> &p2){
	if(p1.second == p2.second) return p1.first > p2.first;
	else return p1.second < p2.second;
}

int sub3(){
	for(int i=1; i<=m; i++)
		use[i]=true;
	if(!check()) return 0;

	vector<pair<int, int>> v;
    for(int i=1; i<=m; i++)
		v.push_back(make_pair(s[i], e[i]));
	sort(v.begin(), v.end(), comp3);

	int ans=1;
	stack<pair<int, int>> st;
	for(auto &e:v){
        if(st.empty()){
			st.push(e);
			continue;
		}
		else{
            if(st.top().first < e.first){
				pair<int, int> piv = st.top(); st.pop();
				int pivCnt=1, norCnt=0;

				while(!st.empty()){
                    if(st.top()==piv) pivCnt++;
                    else norCnt++;
                    st.pop();
				}
				ans=ans*1ll*(myPow(2, pivCnt)-1)%mod*myPow(2, norCnt)%mod;
				st.push(e);
            }
            else st.push(e);
		}
	}

	if(!st.empty()){
		pair<int, int> piv = st.top(); st.pop();
		int pivCnt=1, norCnt=0;

		while(!st.empty()){
			if(st.top()==piv) pivCnt++;
			else norCnt++;
			st.pop();
		}
		ans=ans*1ll*(myPow(2, pivCnt)-1)%mod*myPow(2, norCnt)%mod;
	}

	if(ans<0) ans+=mod;
	return ans;
}

int main(){
#ifndef EVAL
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++)
		scanf("%d %d", &s[i], &e[i]);

    if(m<=20){
		printf("%d", f(1));
		return 0;
	}
	else{
		printf("%d", sub3());
		return 0;
	}
	return 0;
}

Compilation message (stderr)

rail.cpp: In function 'int main()':
rail.cpp:105:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
rail.cpp:107:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &s[i], &e[i]);
                               ^

• Subtask 1: 10 / 10
• Subtask 2: 8 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 27
• Subtask 5: 0 / 30