oj.uz

Submission #20447

# Submission time Handle Problem Language Result Execution time Memory
20447 2017-02-11T14:51:26 Z I_forgot_password(#50, mAng0) 초음속철도 (OJUZ11_rail) C++
0 / 100
 2779 ms 36748 KB 
#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) 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;
    }
    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",sum[pp + gae - 1] * jegop(m) % je);
    else printf("0");
}

Compilation message

rail.cpp: In function 'int main()':
rail.cpp:86:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<cnt.size();i++){
                  ^
rail.cpp:81:9: warning: unused variable 'prv' [-Wunused-variable]
     int prv = -1;
         ^
rail.cpp:73: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:75: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 15876 KB Output isn't correct
2 Correct 0 ms 15876 KB Output is correct
3 Correct 0 ms 15876 KB Output is correct
4 Correct 0 ms 15876 KB Output is correct
5 Correct 0 ms 15876 KB Output is correct
6 Correct 0 ms 15876 KB Output is correct
7 Incorrect 0 ms 15876 KB Output isn't correct
8 Incorrect 0 ms 15876 KB Output isn't correct
9 Correct 0 ms 15876 KB Output is correct
10 Correct 0 ms 15876 KB Output is correct
11 Correct 0 ms 15876 KB Output is correct
12 Incorrect 0 ms 15876 KB Output isn't correct
13 Incorrect 0 ms 15876 KB Output isn't correct
14 Incorrect 0 ms 15876 KB Output isn't correct
15 Incorrect 0 ms 15876 KB Output isn't correct
16 Incorrect 0 ms 15876 KB Output isn't correct
17 Correct 0 ms 15876 KB Output is correct
18 Correct 0 ms 15876 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 15876 KB Output isn't correct
2 Correct 0 ms 15876 KB Output is correct
3 Correct 0 ms 15876 KB Output is correct
4 Correct 0 ms 15876 KB Output is correct
5 Correct 0 ms 15876 KB Output is correct
6 Correct 0 ms 15876 KB Output is correct
7 Incorrect 0 ms 15876 KB Output isn't correct
8 Incorrect 0 ms 15876 KB Output isn't correct
9 Correct 0 ms 15876 KB Output is correct
10 Correct 0 ms 15876 KB Output is correct
11 Correct 0 ms 15876 KB Output is correct
12 Incorrect 0 ms 15876 KB Output isn't correct
13 Incorrect 0 ms 15876 KB Output isn't correct
14 Incorrect 0 ms 15876 KB Output isn't correct
15 Incorrect 0 ms 15876 KB Output isn't correct
16 Incorrect 0 ms 15876 KB Output isn't correct
17 Correct 0 ms 15876 KB Output is correct
18 Correct 0 ms 15876 KB Output is correct
19 Correct 0 ms 15876 KB Output is correct
20 Incorrect 0 ms 15876 KB Output isn't correct
21 Correct 0 ms 15876 KB Output is correct
22 Incorrect 0 ms 15876 KB Output isn't correct
23 Correct 0 ms 15876 KB Output is correct
24 Correct 0 ms 15876 KB Output is correct
25 Incorrect 0 ms 15876 KB Output isn't correct
26 Correct 0 ms 15876 KB Output is correct
27 Correct 0 ms 15876 KB Output is correct
28 Incorrect 0 ms 15876 KB Output isn't correct
29 Correct 0 ms 15876 KB Output is correct
30 Correct 0 ms 15876 KB Output is correct
31 Incorrect 0 ms 15876 KB Output isn't correct
32 Incorrect 0 ms 15876 KB Output isn't correct
33 Correct 0 ms 15876 KB Output is correct
34 Correct 0 ms 15876 KB Output is correct
35 Correct 0 ms 15876 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15876 KB Output is correct
2 Correct 0 ms 15876 KB Output is correct
3 Correct 0 ms 15876 KB Output is correct
4 Correct 13 ms 16016 KB Output is correct
5 Incorrect 939 ms 20512 KB Output isn't correct
6 Correct 569 ms 35164 KB Output is correct
7 Correct 566 ms 34900 KB Output is correct
8 Correct 0 ms 15876 KB Output is correct
9 Correct 543 ms 33844 KB Output is correct
10 Correct 579 ms 34768 KB Output is correct
11 Correct 389 ms 18564 KB Output is correct
12 Correct 589 ms 35164 KB Output is correct
13 Correct 579 ms 34768 KB Output is correct
14 Correct 219 ms 19032 KB Output is correct
15 Correct 333 ms 27376 KB Output is correct
16 Correct 236 ms 19032 KB Output is correct
17 Correct 586 ms 35164 KB Output is correct
18 Correct 579 ms 35164 KB Output is correct
19 Correct 586 ms 32656 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 15876 KB Output isn't correct
2 Correct 0 ms 15876 KB Output is correct
3 Correct 0 ms 15876 KB Output is correct
4 Correct 0 ms 15876 KB Output is correct
5 Correct 0 ms 15876 KB Output is correct
6 Correct 0 ms 15876 KB Output is correct
7 Incorrect 0 ms 15876 KB Output isn't correct
8 Incorrect 0 ms 15876 KB Output isn't correct
9 Correct 0 ms 15876 KB Output is correct
10 Correct 0 ms 15876 KB Output is correct
11 Correct 0 ms 15876 KB Output is correct
12 Incorrect 0 ms 15876 KB Output isn't correct
13 Incorrect 0 ms 15876 KB Output isn't correct
14 Incorrect 0 ms 15876 KB Output isn't correct
15 Incorrect 0 ms 15876 KB Output isn't correct
16 Incorrect 0 ms 15876 KB Output isn't correct
17 Correct 0 ms 15876 KB Output is correct
18 Correct 0 ms 15876 KB Output is correct
19 Correct 0 ms 15876 KB Output is correct
20 Incorrect 0 ms 15876 KB Output isn't correct
21 Correct 0 ms 15876 KB Output is correct
22 Incorrect 0 ms 15876 KB Output isn't correct
23 Correct 0 ms 15876 KB Output is correct
24 Correct 0 ms 15876 KB Output is correct
25 Incorrect 0 ms 15876 KB Output isn't correct
26 Correct 0 ms 15876 KB Output is correct
27 Correct 0 ms 15876 KB Output is correct
28 Incorrect 0 ms 15876 KB Output isn't correct
29 Correct 0 ms 15876 KB Output is correct
30 Correct 0 ms 15876 KB Output is correct
31 Incorrect 0 ms 15876 KB Output isn't correct
32 Incorrect 0 ms 15876 KB Output isn't correct
33 Correct 0 ms 15876 KB Output is correct
34 Correct 0 ms 15876 KB Output is correct
35 Correct 0 ms 15876 KB Output is correct
36 Correct 43 ms 16412 KB Output is correct
37 Incorrect 33 ms 16280 KB Output isn't correct
38 Incorrect 26 ms 16148 KB Output isn't correct
39 Incorrect 3 ms 16016 KB Output isn't correct
40 Correct 3 ms 16148 KB Output is correct
41 Correct 0 ms 16016 KB Output is correct
42 Correct 36 ms 16412 KB Output is correct
43 Incorrect 0 ms 15876 KB Output isn't correct
44 Incorrect 23 ms 16280 KB Output isn't correct
45 Incorrect 6 ms 16016 KB Output isn't correct
46 Correct 16 ms 16148 KB Output is correct
47 Incorrect 29 ms 16148 KB Output isn't correct
48 Correct 26 ms 16148 KB Output is correct
49 Correct 13 ms 16016 KB Output is correct
50 Correct 9 ms 16016 KB Output is correct
51 Correct 13 ms 16016 KB Output is correct
52 Correct 6 ms 16008 KB Output is correct
53 Correct 3 ms 16016 KB Output is correct
54 Correct 16 ms 16016 KB Output is correct
55 Correct 3 ms 16016 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 15876 KB Output isn't correct
2 Correct 0 ms 15876 KB Output is correct
3 Correct 0 ms 15876 KB Output is correct
4 Correct 0 ms 15876 KB Output is correct
5 Correct 0 ms 15876 KB Output is correct
6 Correct 0 ms 15876 KB Output is correct
7 Incorrect 0 ms 15876 KB Output isn't correct
8 Incorrect 0 ms 15876 KB Output isn't correct
9 Correct 0 ms 15876 KB Output is correct
10 Correct 0 ms 15876 KB Output is correct
11 Correct 0 ms 15876 KB Output is correct
12 Incorrect 0 ms 15876 KB Output isn't correct
13 Incorrect 0 ms 15876 KB Output isn't correct
14 Incorrect 0 ms 15876 KB Output isn't correct
15 Incorrect 0 ms 15876 KB Output isn't correct
16 Incorrect 0 ms 15876 KB Output isn't correct
17 Correct 0 ms 15876 KB Output is correct
18 Correct 0 ms 15876 KB Output is correct
19 Correct 0 ms 15876 KB Output is correct
20 Incorrect 0 ms 15876 KB Output isn't correct
21 Correct 0 ms 15876 KB Output is correct
22 Incorrect 0 ms 15876 KB Output isn't correct
23 Correct 0 ms 15876 KB Output is correct
24 Correct 0 ms 15876 KB Output is correct
25 Incorrect 0 ms 15876 KB Output isn't correct
26 Correct 0 ms 15876 KB Output is correct
27 Correct 0 ms 15876 KB Output is correct
28 Incorrect 0 ms 15876 KB Output isn't correct
29 Correct 0 ms 15876 KB Output is correct
30 Correct 0 ms 15876 KB Output is correct
31 Incorrect 0 ms 15876 KB Output isn't correct
32 Incorrect 0 ms 15876 KB Output isn't correct
33 Correct 0 ms 15876 KB Output is correct
34 Correct 0 ms 15876 KB Output is correct
35 Correct 0 ms 15876 KB Output is correct
36 Correct 0 ms 15876 KB Output is correct
37 Correct 0 ms 15876 KB Output is correct
38 Correct 0 ms 15876 KB Output is correct
39 Correct 13 ms 16016 KB Output is correct
40 Incorrect 939 ms 20512 KB Output isn't correct
41 Correct 569 ms 35164 KB Output is correct
42 Correct 566 ms 34900 KB Output is correct
43 Correct 0 ms 15876 KB Output is correct
44 Correct 543 ms 33844 KB Output is correct
45 Correct 579 ms 34768 KB Output is correct
46 Correct 389 ms 18564 KB Output is correct
47 Correct 589 ms 35164 KB Output is correct
48 Correct 579 ms 34768 KB Output is correct
49 Correct 219 ms 19032 KB Output is correct
50 Correct 333 ms 27376 KB Output is correct
51 Correct 236 ms 19032 KB Output is correct
52 Correct 586 ms 35164 KB Output is correct
53 Correct 579 ms 35164 KB Output is correct
54 Correct 586 ms 32656 KB Output is correct
55 Correct 43 ms 16412 KB Output is correct
56 Incorrect 33 ms 16280 KB Output isn't correct
57 Incorrect 26 ms 16148 KB Output isn't correct
58 Incorrect 3 ms 16016 KB Output isn't correct
59 Correct 3 ms 16148 KB Output is correct
60 Correct 0 ms 16016 KB Output is correct
61 Correct 36 ms 16412 KB Output is correct
62 Incorrect 0 ms 15876 KB Output isn't correct
63 Incorrect 23 ms 16280 KB Output isn't correct
64 Incorrect 6 ms 16016 KB Output isn't correct
65 Correct 16 ms 16148 KB Output is correct
66 Incorrect 29 ms 16148 KB Output isn't correct
67 Correct 26 ms 16148 KB Output is correct
68 Correct 13 ms 16016 KB Output is correct
69 Correct 9 ms 16016 KB Output is correct
70 Correct 13 ms 16016 KB Output is correct
71 Correct 6 ms 16008 KB Output is correct
72 Correct 3 ms 16016 KB Output is correct
73 Correct 16 ms 16016 KB Output is correct
74 Correct 3 ms 16016 KB Output is correct
75 Incorrect 2779 ms 36748 KB Output isn't correct
76 Incorrect 1703 ms 30280 KB Output isn't correct
77 Incorrect 1018 ms 19032 KB Output isn't correct
78 Incorrect 246 ms 19032 KB Output isn't correct
79 Correct 93 ms 19032 KB Output is correct
80 Correct 2776 ms 36748 KB Output is correct
81 Incorrect 29 ms 16148 KB Output isn't correct
82 Incorrect 2346 ms 34636 KB Output isn't correct
83 Incorrect 236 ms 19032 KB Output isn't correct
84 Incorrect 1923 ms 31996 KB Output isn't correct
85 Incorrect 1923 ms 27376 KB Output isn't correct
86 Incorrect 1883 ms 27376 KB Output isn't correct
87 Correct 479 ms 19032 KB Output is correct
88 Incorrect 433 ms 19032 KB Output isn't correct
89 Incorrect 2733 ms 36748 KB Output isn't correct
90 Incorrect 2773 ms 36748 KB Output isn't correct
91 Incorrect 2766 ms 36748 KB Output isn't correct
92 Correct 99 ms 19032 KB Output is correct
93 Correct 1896 ms 27244 KB Output is correct
94 Incorrect 2756 ms 36748 KB Output isn't correct
95 Incorrect 2723 ms 36748 KB Output isn't correct