oj.uz

Submission #71929

# Submission time Handle Problem Language Result Execution time Memory
71929 2018-08-25T23:00:50 Z Bruteforceman Port Facility (JOI17_port_facility) C++11
100 / 100
 4891 ms 651860 KB 
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef pair<int, int> pii;
    const int MX=1000010, inf=2e9, MOD=1e9+7;
     
    int n, S[MX], E[MX];
     
    inline pii _min(const pii &a, const pii &b){ return a.first<b.first ? a : b; }
    inline pii _max(const pii &a, const pii &b){ return a.first>b.first ? a : b; }
    const pii pninf=pii(inf,-1), pxinf=pii(0, -1);
     
    pii ntree[1<<22], xtree[1<<22];
     
    void init(){
        for(int i=1; i<(1<<22); i++)
            ntree[i]=pninf, xtree[i]=pxinf;
    }
     
    pii mn(int v, int s, int e, int l, int r){
        if(l<=s && e<=r) return ntree[v];
        int m=(s+e)/2;
        if(r<=m) return mn(v*2,s,(s+e)/2,l,r);
        if(m+1<=l) return mn(v*2+1,(s+e)/2+1,e,l,r);
        return _min(mn(v*2,s,(s+e)/2,l,r), mn(v*2+1,(s+e)/2+1,e,l,r));
    }
    pii mx(int v, int s, int e, int l, int r){
        if(l<=s && e<=r) return xtree[v];
        int m=(s+e)/2;
        if(r<=m) return mx(v*2,s,(s+e)/2,l,r);
        if(m+1<=l) return mx(v*2+1,(s+e)/2+1,e,l,r);
        return _max(mx(v*2,s,(s+e)/2,l,r), mx(v*2+1,(s+e)/2+1,e,l,r));
    }
    pii mn(int l, int r){
        return mn(1,1,2*n,l,r);
    }
    pii mx(int l, int r){
        return mx(1,1,2*n,l,r);
    }
     
    void nupt(int v, int s, int e, int pos, const pii &val){
        if(s==e){
            ntree[v]=val;
            return;
        }
        int m=(s+e)/2;
        if(pos<=m) nupt(v*2,s,(s+e)/2,pos,val);
        else nupt(v*2+1,(s+e)/2+1,e,pos,val);
        ntree[v]=_min(ntree[v*2], ntree[v*2+1]);
    }
    void xupt(int v, int s, int e, int pos, const pii &val){
        if(s==e){
            xtree[v]=val;
            return;
        }
        int m=(s+e)/2;
        if(pos<=m) xupt(v*2,s,(s+e)/2,pos,val);
        else xupt(v*2+1,(s+e)/2+1,e,pos,val);
        xtree[v]=_max(xtree[v*2], xtree[v*2+1]);
    }
     
    void nupt(int pos, const pii &val){
        nupt(1,1,2*n,pos,val);
    }
     
    void xupt(int pos, const pii &val){
        xupt(1,1,2*n,pos,val);
    }
     
    bool vis[MX];
    int col[MX];
     
    void dfs(int v, int c=0){
        vis[v]=true; col[v]=c;
        nupt(E[v], pninf);
        xupt(S[v], pxinf);
        while(true){
            pii q=mx(S[v], E[v]);
            if(q.first<E[v]) break;
            else dfs(q.second, 1-c);
        }
        while(true){
            pii q=mn(S[v], E[v]);
            if(S[v]<q.first) break;
            else dfs(q.second, 1-c);
        }
    }
     
    int H[2*MX], cnt[2*MX];
    bool valid(){
        for(int i=1; i<=n; i++){
            assert(vis[i]);
            if(col[i]!=0) continue;
            cnt[S[i]]++, cnt[E[i]+1]--;
        }
        for(int i=1, now=0; i<=2*n+1; i++){
            now+=cnt[i]; cnt[i]=0;
            H[i]=now;
        }
        for(int i=1; i<=n; i++){
            if(col[i]!=0) continue;
            if(H[S[i]]!=H[E[i]]) return false;
        }
        for(int i=1; i<=n; i++){
            if(col[i]!=1) continue;
            cnt[S[i]]++, cnt[E[i]+1]--;
        }
        for(int i=1, now=0; i<=2*n+1; i++){
            now+=cnt[i]; cnt[i]=0;
            H[i]=now;
        }
        for(int i=1; i<=n; i++){
            if(col[i]!=1) continue;
            if(H[S[i]]!=H[E[i]]) return false;
        }
        return true;
    }
     
    int main(){
        ios::sync_with_stdio(0); cin.tie(0);
        cin>>n;
        init();
        for(int i=1; i<=n; i++){
            cin>>S[i]>>E[i];
            nupt(E[i], pii(S[i], i));
            xupt(S[i], pii(E[i], i));
        }
        int ans=1;
        for(int i=1; i<=n; i++){
            if(!vis[i]) dfs(i), ans=ans*2%MOD;
        }
        cout<<(valid() ? ans : 0);
        return 0;
    }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 66040 KB Output is correct
2 Correct 62 ms 66152 KB Output is correct
3 Correct 52 ms 66264 KB Output is correct
4 Correct 55 ms 66376 KB Output is correct
5 Correct 59 ms 66376 KB Output is correct
6 Correct 62 ms 66424 KB Output is correct
7 Correct 70 ms 66424 KB Output is correct
8 Correct 52 ms 66424 KB Output is correct
9 Correct 54 ms 66424 KB Output is correct
10 Correct 61 ms 66424 KB Output is correct
11 Correct 56 ms 66424 KB Output is correct
12 Correct 59 ms 66424 KB Output is correct
13 Correct 53 ms 66428 KB Output is correct
14 Correct 52 ms 66428 KB Output is correct
15 Correct 55 ms 66452 KB Output is correct
16 Correct 53 ms 66500 KB Output is correct
17 Correct 52 ms 66500 KB Output is correct
18 Correct 52 ms 66500 KB Output is correct
19 Correct 64 ms 66500 KB Output is correct
20 Correct 55 ms 66500 KB Output is correct
21 Correct 57 ms 66604 KB Output is correct
22 Correct 65 ms 66604 KB Output is correct
23 Correct 56 ms 66604 KB Output is correct
24 Correct 52 ms 66604 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 66040 KB Output is correct
2 Correct 62 ms 66152 KB Output is correct
3 Correct 52 ms 66264 KB Output is correct
4 Correct 55 ms 66376 KB Output is correct
5 Correct 59 ms 66376 KB Output is correct
6 Correct 62 ms 66424 KB Output is correct
7 Correct 70 ms 66424 KB Output is correct
8 Correct 52 ms 66424 KB Output is correct
9 Correct 54 ms 66424 KB Output is correct
10 Correct 61 ms 66424 KB Output is correct
11 Correct 56 ms 66424 KB Output is correct
12 Correct 59 ms 66424 KB Output is correct
13 Correct 53 ms 66428 KB Output is correct
14 Correct 52 ms 66428 KB Output is correct
15 Correct 55 ms 66452 KB Output is correct
16 Correct 53 ms 66500 KB Output is correct
17 Correct 52 ms 66500 KB Output is correct
18 Correct 52 ms 66500 KB Output is correct
19 Correct 64 ms 66500 KB Output is correct
20 Correct 55 ms 66500 KB Output is correct
21 Correct 57 ms 66604 KB Output is correct
22 Correct 65 ms 66604 KB Output is correct
23 Correct 56 ms 66604 KB Output is correct
24 Correct 52 ms 66604 KB Output is correct
25 Correct 68 ms 66620 KB Output is correct
26 Correct 57 ms 66620 KB Output is correct
27 Correct 55 ms 66644 KB Output is correct
28 Correct 74 ms 66720 KB Output is correct
29 Correct 65 ms 66860 KB Output is correct
30 Correct 59 ms 66860 KB Output is correct
31 Correct 57 ms 66860 KB Output is correct
32 Correct 59 ms 66860 KB Output is correct
33 Correct 56 ms 66860 KB Output is correct
34 Correct 58 ms 66880 KB Output is correct
35 Correct 53 ms 66916 KB Output is correct
36 Correct 64 ms 66916 KB Output is correct
37 Correct 55 ms 66928 KB Output is correct
38 Correct 64 ms 66948 KB Output is correct
39 Correct 62 ms 66948 KB Output is correct
40 Correct 62 ms 67080 KB Output is correct
41 Correct 66 ms 67224 KB Output is correct
42 Correct 64 ms 67224 KB Output is correct
43 Correct 61 ms 67224 KB Output is correct
44 Correct 58 ms 67224 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 66040 KB Output is correct
2 Correct 62 ms 66152 KB Output is correct
3 Correct 52 ms 66264 KB Output is correct
4 Correct 55 ms 66376 KB Output is correct
5 Correct 59 ms 66376 KB Output is correct
6 Correct 62 ms 66424 KB Output is correct
7 Correct 70 ms 66424 KB Output is correct
8 Correct 52 ms 66424 KB Output is correct
9 Correct 54 ms 66424 KB Output is correct
10 Correct 61 ms 66424 KB Output is correct
11 Correct 56 ms 66424 KB Output is correct
12 Correct 59 ms 66424 KB Output is correct
13 Correct 53 ms 66428 KB Output is correct
14 Correct 52 ms 66428 KB Output is correct
15 Correct 55 ms 66452 KB Output is correct
16 Correct 53 ms 66500 KB Output is correct
17 Correct 52 ms 66500 KB Output is correct
18 Correct 52 ms 66500 KB Output is correct
19 Correct 64 ms 66500 KB Output is correct
20 Correct 55 ms 66500 KB Output is correct
21 Correct 57 ms 66604 KB Output is correct
22 Correct 65 ms 66604 KB Output is correct
23 Correct 56 ms 66604 KB Output is correct
24 Correct 52 ms 66604 KB Output is correct
25 Correct 68 ms 66620 KB Output is correct
26 Correct 57 ms 66620 KB Output is correct
27 Correct 55 ms 66644 KB Output is correct
28 Correct 74 ms 66720 KB Output is correct
29 Correct 65 ms 66860 KB Output is correct
30 Correct 59 ms 66860 KB Output is correct
31 Correct 57 ms 66860 KB Output is correct
32 Correct 59 ms 66860 KB Output is correct
33 Correct 56 ms 66860 KB Output is correct
34 Correct 58 ms 66880 KB Output is correct
35 Correct 53 ms 66916 KB Output is correct
36 Correct 64 ms 66916 KB Output is correct
37 Correct 55 ms 66928 KB Output is correct
38 Correct 64 ms 66948 KB Output is correct
39 Correct 62 ms 66948 KB Output is correct
40 Correct 62 ms 67080 KB Output is correct
41 Correct 66 ms 67224 KB Output is correct
42 Correct 64 ms 67224 KB Output is correct
43 Correct 61 ms 67224 KB Output is correct
44 Correct 58 ms 67224 KB Output is correct
45 Correct 281 ms 71568 KB Output is correct
46 Correct 315 ms 73192 KB Output is correct
47 Correct 289 ms 73704 KB Output is correct
48 Correct 287 ms 75732 KB Output is correct
49 Correct 314 ms 76356 KB Output is correct
50 Correct 305 ms 78252 KB Output is correct
51 Correct 299 ms 79384 KB Output is correct
52 Correct 245 ms 79876 KB Output is correct
53 Correct 339 ms 81188 KB Output is correct
54 Correct 332 ms 85636 KB Output is correct
55 Correct 292 ms 85636 KB Output is correct
56 Correct 288 ms 86468 KB Output is correct
57 Correct 254 ms 86468 KB Output is correct
58 Correct 271 ms 87452 KB Output is correct
59 Correct 286 ms 88772 KB Output is correct
60 Correct 284 ms 89972 KB Output is correct
61 Correct 297 ms 91376 KB Output is correct
62 Correct 293 ms 92576 KB Output is correct
63 Correct 294 ms 93880 KB Output is correct
64 Correct 284 ms 95048 KB Output is correct
65 Correct 395 ms 99436 KB Output is correct
66 Correct 421 ms 100888 KB Output is correct
67 Correct 322 ms 100888 KB Output is correct
68 Correct 329 ms 101752 KB Output is correct
69 Correct 309 ms 102828 KB Output is correct
70 Correct 295 ms 104048 KB Output is correct
71 Correct 298 ms 107228 KB Output is correct
72 Correct 293 ms 108384 KB Output is correct
73 Correct 307 ms 108472 KB Output is correct
74 Correct 297 ms 109856 KB Output is correct
75 Correct 222 ms 110860 KB Output is correct
76 Correct 239 ms 113404 KB Output is correct
77 Correct 274 ms 114788 KB Output is correct
78 Correct 331 ms 114788 KB Output is correct
79 Correct 321 ms 114788 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 66040 KB Output is correct
2 Correct 62 ms 66152 KB Output is correct
3 Correct 52 ms 66264 KB Output is correct
4 Correct 55 ms 66376 KB Output is correct
5 Correct 59 ms 66376 KB Output is correct
6 Correct 62 ms 66424 KB Output is correct
7 Correct 70 ms 66424 KB Output is correct
8 Correct 52 ms 66424 KB Output is correct
9 Correct 54 ms 66424 KB Output is correct
10 Correct 61 ms 66424 KB Output is correct
11 Correct 56 ms 66424 KB Output is correct
12 Correct 59 ms 66424 KB Output is correct
13 Correct 53 ms 66428 KB Output is correct
14 Correct 52 ms 66428 KB Output is correct
15 Correct 55 ms 66452 KB Output is correct
16 Correct 53 ms 66500 KB Output is correct
17 Correct 52 ms 66500 KB Output is correct
18 Correct 52 ms 66500 KB Output is correct
19 Correct 64 ms 66500 KB Output is correct
20 Correct 55 ms 66500 KB Output is correct
21 Correct 57 ms 66604 KB Output is correct
22 Correct 65 ms 66604 KB Output is correct
23 Correct 56 ms 66604 KB Output is correct
24 Correct 52 ms 66604 KB Output is correct
25 Correct 68 ms 66620 KB Output is correct
26 Correct 57 ms 66620 KB Output is correct
27 Correct 55 ms 66644 KB Output is correct
28 Correct 74 ms 66720 KB Output is correct
29 Correct 65 ms 66860 KB Output is correct
30 Correct 59 ms 66860 KB Output is correct
31 Correct 57 ms 66860 KB Output is correct
32 Correct 59 ms 66860 KB Output is correct
33 Correct 56 ms 66860 KB Output is correct
34 Correct 58 ms 66880 KB Output is correct
35 Correct 53 ms 66916 KB Output is correct
36 Correct 64 ms 66916 KB Output is correct
37 Correct 55 ms 66928 KB Output is correct
38 Correct 64 ms 66948 KB Output is correct
39 Correct 62 ms 66948 KB Output is correct
40 Correct 62 ms 67080 KB Output is correct
41 Correct 66 ms 67224 KB Output is correct
42 Correct 64 ms 67224 KB Output is correct
43 Correct 61 ms 67224 KB Output is correct
44 Correct 58 ms 67224 KB Output is correct
45 Correct 281 ms 71568 KB Output is correct
46 Correct 315 ms 73192 KB Output is correct
47 Correct 289 ms 73704 KB Output is correct
48 Correct 287 ms 75732 KB Output is correct
49 Correct 314 ms 76356 KB Output is correct
50 Correct 305 ms 78252 KB Output is correct
51 Correct 299 ms 79384 KB Output is correct
52 Correct 245 ms 79876 KB Output is correct
53 Correct 339 ms 81188 KB Output is correct
54 Correct 332 ms 85636 KB Output is correct
55 Correct 292 ms 85636 KB Output is correct
56 Correct 288 ms 86468 KB Output is correct
57 Correct 254 ms 86468 KB Output is correct
58 Correct 271 ms 87452 KB Output is correct
59 Correct 286 ms 88772 KB Output is correct
60 Correct 284 ms 89972 KB Output is correct
61 Correct 297 ms 91376 KB Output is correct
62 Correct 293 ms 92576 KB Output is correct
63 Correct 294 ms 93880 KB Output is correct
64 Correct 284 ms 95048 KB Output is correct
65 Correct 395 ms 99436 KB Output is correct
66 Correct 421 ms 100888 KB Output is correct
67 Correct 322 ms 100888 KB Output is correct
68 Correct 329 ms 101752 KB Output is correct
69 Correct 309 ms 102828 KB Output is correct
70 Correct 295 ms 104048 KB Output is correct
71 Correct 298 ms 107228 KB Output is correct
72 Correct 293 ms 108384 KB Output is correct
73 Correct 307 ms 108472 KB Output is correct
74 Correct 297 ms 109856 KB Output is correct
75 Correct 222 ms 110860 KB Output is correct
76 Correct 239 ms 113404 KB Output is correct
77 Correct 274 ms 114788 KB Output is correct
78 Correct 331 ms 114788 KB Output is correct
79 Correct 321 ms 114788 KB Output is correct
80 Correct 3214 ms 156044 KB Output is correct
81 Correct 3418 ms 170300 KB Output is correct
82 Correct 3278 ms 183612 KB Output is correct
83 Correct 3317 ms 199416 KB Output is correct
84 Correct 3334 ms 214424 KB Output is correct
85 Correct 3363 ms 227488 KB Output is correct
86 Correct 3243 ms 243132 KB Output is correct
87 Correct 2844 ms 256136 KB Output is correct
88 Correct 3669 ms 270692 KB Output is correct
89 Correct 3174 ms 316724 KB Output is correct
90 Correct 3130 ms 316724 KB Output is correct
91 Correct 3192 ms 330220 KB Output is correct
92 Correct 2810 ms 330220 KB Output is correct
93 Correct 2802 ms 343636 KB Output is correct
94 Correct 3226 ms 358084 KB Output is correct
95 Correct 3461 ms 372784 KB Output is correct
96 Correct 3317 ms 387276 KB Output is correct
97 Correct 3161 ms 401908 KB Output is correct
98 Correct 2950 ms 416516 KB Output is correct
99 Correct 3112 ms 431048 KB Output is correct
100 Correct 4810 ms 476984 KB Output is correct
101 Correct 4891 ms 491576 KB Output is correct
102 Correct 3310 ms 491576 KB Output is correct
103 Correct 3361 ms 504928 KB Output is correct
104 Correct 3273 ms 517816 KB Output is correct
105 Correct 3136 ms 532456 KB Output is correct
106 Correct 3178 ms 564548 KB Output is correct
107 Correct 3181 ms 579024 KB Output is correct
108 Correct 3170 ms 583144 KB Output is correct
109 Correct 3305 ms 597628 KB Output is correct
110 Correct 2544 ms 621968 KB Output is correct
111 Correct 2721 ms 637408 KB Output is correct
112 Correct 2743 ms 651860 KB Output is correct
113 Correct 3275 ms 651860 KB Output is correct
114 Correct 3242 ms 651860 KB Output is correct