Submission #20493

#	Time	Username	Problem	Language	Result	Execution time	Memory
20493		볼빨간민돌이 (#35)	초음속철도 (OJUZ11_rail)	C++11	18 / 100	513 ms	7104 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.first == p2.first) return p1.second > p2.second;
	else return p1.first < p2.first;
}

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;
	pair<int, int> piv;
	int pivCnt=0, norCnt=0;
	for(auto &e:v){
        if(pivCnt==0) pivCnt++, piv=e;
        else{
            if(e.first >= piv.second){
				ans=ans*1ll*(myPow(2, pivCnt)-1)%mod*myPow(2, norCnt)%mod;
				pivCnt=1, norCnt=0, piv=e;
			}
			else{
				if(e==piv) pivCnt++;
				else norCnt++;
			}
        }
	}
	if(pivCnt) 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\n", f(1));
		return 0;
	}
	else{
		printf("%d\n", sub3());
		return 0;
	}
	return 0;
}

Compilation message (stderr)

rail.cpp: In function 'int main()':
rail.cpp:87: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:89: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