제출 #20449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20449		I_forgot_password (#35)	초음속철도 (OJUZ11_rail)	C++98	100 / 100	2813 ms	36748 KiB

rail

#include<bits/stdc++.h>
#define je 1000000007
#define pp 524288
using namespace std;

pair<int,int> train[200001];
vector<int> cnt;
map<int,int> dict;
long long sum[1048576];
int div2[1048576];
int can;
int gae=0;

long long jegop(int left){
    if(!left) return 1;
    else if(left & 1){
        long long res = jegop(left / 2);
        return (res * res * 2) % je;
    }else{
        long long res = jegop(left / 2);
        return res * res % je;
    }
}


void segPlus(int place,long long what,int ss,int ee,int idx){
    //printf("segPlus: %d %lld %d %d %d ?%lld %d\n",place,what,ss,ee,idx,sum[idx],div2[idx]);
    if(div2[idx]){
        sum[idx] = sum[idx] * jegop(je - 1 - div2[idx]) % je;
    }
    sum[idx] = (sum[idx] + what) % je;
    if(ss==ee){
        div2[idx] = 0; return;
    }
    div2[idx*2] += div2[idx]; div2[idx*2+1] += div2[idx]; div2[idx] = 0;
    int mid = (ss+ee)/2;
    if(place <= mid){
        segPlus(place,what,ss,mid,idx*2);
    }else{
        segPlus(place,what,mid+1,ee,idx*2+1);
    }
}
long long getsum(int from,int to,int ss,int ee,int idx){
    //printf("getsum: %d %d %d %d %d ?%lld %d\n",from,to,ss,ee,idx,sum[idx],div2[idx]);
    long long retval,new_minus;
    if(div2[idx]){
        sum[idx] = sum[idx] * jegop(je - 1 - div2[idx]) % je;
    }
    if(ss!=ee){
        div2[idx*2] += div2[idx];
        div2[idx*2+1] += div2[idx];
        div2[idx] = 0;
    }else{
        div2[idx] = 0;
    }
    if(from == ss && to == ee){
        div2[idx]++;
        return sum[idx];
    }else{
        int mid = (ss+ee)/2;
        if(to <= mid){
            retval = getsum(from,to,ss,mid,idx*2);
        }else if(from > mid){
            retval = getsum(from,to,mid+1,ee,idx*2+1);
        }else{
            retval = (getsum(from,mid,ss,mid,idx*2) + getsum(mid+1,to,mid+1,ee,idx*2+1)) % je;
        }
        if(retval%2) new_minus = (retval + je) / 2;
        else new_minus = (retval) / 2;
        sum[idx] = (sum[idx] + je - new_minus) % je;
        return retval;
    }
}

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;
    segPlus(0,1,0,pp-1,1);
    for(int j=0;j<m;j++){
        int from = dict[train[j].first];
        int to = dict[train[j].second];
        //printf("%d, %d\n",from,to);
        if(can < from){
            printf("%d",0);
            return 0;
        }
        can = max(can,to);
        long long retval = getsum(from,to-1,0,pp-1,1);
        if(retval%2==1) retval = (retval + je) / 2;
        else retval = retval / 2;
        //printf("%lld\n",retval);
        segPlus(to,retval,0,pp-1,1);
    }
    segPlus(gae-1,0,0,pp-1,1);
    if(can == gae-1) printf("%lld",getsum(gae-1,gae-1,0,pp-1,1) * jegop(m) % je);
    else printf("0");
}

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp: In function 'int main()':
rail.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<cnt.size();i++){
                  ^
rail.cpp:85:9: warning: unused variable 'prv' [-Wunused-variable]
     int prv = -1;
         ^
rail.cpp:77: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:79: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: 25 / 25
• Subtask 4: 27 / 27
• Subtask 5: 30 / 30