Submission #20433

#	Time	Username	Problem	Language	Result	Execution time	Memory
20433		I_forgot_password (#35)	초음속철도 (OJUZ11_rail)	C++98	45 / 100	3000 ms	28676 KiB

rail

#include<bits/stdc++.h>
#define je 1000000007
using namespace std;
pair<int,int> train[200001];
vector<int> cnt;
map<int,int> dict;
long long sum[524288];
long long dp[10001];
int can[10001];
int gae=0;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&(train[i].first),&(train[i].second));
        cnt.push_back(train[i].first);
        cnt.push_back(train[i].second);
    }
    cnt.push_back(-1);
    sort(cnt.begin(),cnt.end());
    int prv = -1;
    if(cnt[1] != 1 || cnt[(int)cnt.size() - 1] != n){
        printf("0");
        return 0;
    }
    for(int i=1;i<cnt.size();i++){
        if(cnt[i-1] != cnt[i]){
            dict[cnt[i]] = gae++;
        }
    }
    sort(train,train+m);
    can[0] = 1; dp[0] = 1;
    for(int j=0;j<m;j++){
        int from = dict[train[j].first];
        int to = dict[train[j].second];
        for(int i=from;i<to;i++){
            if(can[i]){
                can[to] = 1;
                break;
            }
        }
        long long sum = 0;
        for(int i=from;i<to;i++){
            sum = (sum + dp[i]) % je;
        }
        for(int i=to;i<gae;i++){
            dp[i] = (dp[i] * 2) % je;
        }
        dp[to] = (dp[to] + sum) % je;
        /*for(int i=0;i<gae;i++){
            printf("(%d,%lld)\n",can[i],dp[i]);
        }*/
    }
    if(!can[gae-1]){
        printf("0");
    }else{
        printf("%lld",dp[gae-1]);
    }

}

Compilation message (stderr)

rail.cpp: In function 'int main()':
rail.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<cnt.size();i++){
                  ^
rail.cpp:21:9: warning: unused variable 'prv' [-Wunused-variable]
     int prv = -1;
         ^
rail.cpp:13: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:15:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&(train[i].first),&(train[i].second));
                                                           ^

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