oj.uz

Submission #232960

# Submission time Handle Problem Language Result Execution time Memory
232960 2020-05-18T18:58:27 Z thebes Port Facility (JOI17_port_facility) C++14
100 / 100
 3951 ms 682188 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
#define F first
#define S second
#define pb push_back

const int MN = 1e6+6, mod = 1e9+7;
int N, i, j, x, y, vs[MN], on[MN], col[MN], cur, ans=1;
pii arr[MN], evt[2*MN]; stack<int> stk[2]; queue<int> go;

struct SegmentTree{ // range update, point query
    pii *st[6*MN];
    int sz[6*MN], n;
    inline void init(int N){
        n = N;
    }
    void pre(int i,int s,int e,int ss,int se){
        if(s>=ss&&e<=se) sz[i]++;
        else if((s+e)/2<ss) pre(2*i+1,(s+e)/2+1,e,ss,se);
        else if((s+e)/2>=se) pre(2*i,s,(s+e)/2,ss,se);
        else pre(2*i,s,(s+e)/2,ss,se), pre(2*i+1,(s+e)/2+1,e,ss,se);
    }
    inline void pre(int s,int e){
        pre(1,1,n,s,e);
    }
    void build(int i,int s,int e){
        if(s!=e){
            build(2*i,s,(s+e)/2);
            build(2*i+1,(s+e)/2+1,e);
        }
        st[i]=(pii*)malloc(sz[i]*sizeof(pii));
        sz[i]=-1;
    }
    inline void build(){
        build(1,1,n);
    }
    void upd(int i,int s,int e,int ss,int se,int id,int y){
        if(s>=ss&&e<=se) st[i][++sz[i]]={y,id};
        else if((s+e)/2<ss) upd(2*i+1,(s+e)/2+1,e,ss,se,id,y);
        else if((s+e)/2>=se) upd(2*i,s,(s+e)/2,ss,se,id,y);
        else upd(2*i,s,(s+e)/2,ss,se,id,y), upd(2*i+1,(s+e)/2+1,e,ss,se,id,y);
    }
    inline void upd(int s,int e,int id,int y){
        upd(1,1,n,s,e,id,y);
    }
    void qu(int i,int s,int e,int idx,int y){
        while(sz[i]>=0&&st[i][sz[i]].F<=y){
            if(!vs[st[i][sz[i]].S]){
                vs[st[i][sz[i]].S]=1;
                col[st[i][sz[i]].S]=!col[cur];
                go.push(st[i][sz[i]].S);
            }
            sz[i]--;
        }
        if(s!=e){
            if((s+e)/2<idx) qu(2*i+1,(s+e)/2+1,e,idx,y);
            else qu(2*i,s,(s+e)/2,idx,y);
        }
    }
    inline void qu(int idx,int y){
        qu(1,1,n,idx,y);
    }
}st;

struct SegmentTree2{ // point update, range query
    pii *st[6*MN];
    int sz[6*MN], n;
    inline void init(int N){
        n = N;
    }
    void pre(int i,int s,int e,int idx){
        sz[i]++;
        if(s!=e){
            if((s+e)/2<idx) pre(2*i+1,(s+e)/2+1,e,idx);
            else pre(2*i,s,(s+e)/2,idx);
        }
    }
    inline void pre(int idx){
        pre(1,1,n,idx);
    }
    void build(int i,int s,int e){
        st[i]=(pii*)malloc(sz[i]*sizeof(pii));
        sz[i]=-1;
        if(s!=e){
            build(2*i,s,(s+e)/2);
            build(2*i+1,(s+e)/2+1,e);
        }
    }
    inline void build(){
        build(1,1,n);
    }
    void upd(int i,int s,int e,int idx,int id,int y){
        st[i][++sz[i]]={y,id};
        if(s!=e){
            if((s+e)/2<idx) upd(2*i+1,(s+e)/2+1,e,idx,id,y);
            else upd(2*i,s,(s+e)/2,idx,id,y);
        }
    }
    inline void upd(int idx,int id,int y){
        upd(1,1,n,idx,id,y);
    }
    void qu(int i,int s,int e,int ss,int se,int y){
        if(s>=ss&&e<=se){
            while(sz[i]>=0&&st[i][sz[i]].F>=y){
                if(!vs[st[i][sz[i]].S]){
                    vs[st[i][sz[i]].S]=1;
                    col[st[i][sz[i]].S]=!col[cur];
                    go.push(st[i][sz[i]].S);
                }
                sz[i]--;
            }
        }
        else if((s+e)/2<ss) qu(2*i+1,(s+e)/2+1,e,ss,se,y);
        else if((s+e)/2>=se) qu(2*i,s,(s+e)/2,ss,se,y);
        else qu(2*i,s,(s+e)/2,ss,se,y), qu(2*i+1,(s+e)/2+1,e,ss,se,y);
    }
    inline void qu(int s,int e,int y){
        qu(1,1,n,s,e,y);
    }
}st2;

int main(){
    scanf("%d",&N);
    st.init(2*N), st2.init(2*N);
    for(i=1;i<=N;i++)
        scanf("%d%d",&arr[i].F,&arr[i].S);
    sort(arr+1,arr+N+1,[](pii i,pii j){return i.S<j.S;});
    for(i=N;i>=1;i--)
        st.pre(arr[i].F,arr[i].S);
    for(i=1;i<=N;i++)
        st2.pre(arr[i].F);
    st.build(), st2.build();
    for(i=N;i>=1;i--)
        st.upd(arr[i].F,arr[i].S,i,arr[i].S);
    for(i=1;i<=N;i++)
        st2.upd(arr[i].F,i,arr[i].S);
    for(i=1;i<=N;i++){
        if(!vs[i]){
            ans = 2LL*ans%mod;
            vs[i] = 1;
            go.push(i);
            while(go.size()){
                cur=go.front(); go.pop();
                st.qu(arr[cur].F,arr[cur].S);
                st2.qu(arr[cur].F,arr[cur].S,arr[cur].S);
            }
        }
    }
    for(i=1;i<=N;i++){
        evt[2*i-1]={arr[i].F, i};
        evt[2*i]={arr[i].S, i};
    }
    sort(evt+1,evt+2*N+1,[](pii i,pii j){return i.F<j.F;});
    for(i=1;i<=2*N;i++){
        cur = evt[i].S;
        if(on[cur]){
            if(stk[col[cur]].empty()||stk[col[cur]].top()!=cur){
                ans = 0;
                break;
            }
            stk[col[cur]].pop();
        }
        else stk[col[cur]].push(cur);
        on[cur]=!on[cur];
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message

port_facility.cpp: In function 'int main()':
port_facility.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
port_facility.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&arr[i].F,&arr[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 8 ms 1408 KB Output is correct
26 Correct 8 ms 1408 KB Output is correct
27 Correct 8 ms 1408 KB Output is correct
28 Correct 7 ms 1408 KB Output is correct
29 Correct 8 ms 1408 KB Output is correct
30 Correct 8 ms 1408 KB Output is correct
31 Correct 8 ms 1408 KB Output is correct
32 Correct 8 ms 1408 KB Output is correct
33 Correct 8 ms 1328 KB Output is correct
34 Correct 7 ms 1408 KB Output is correct
35 Correct 7 ms 1280 KB Output is correct
36 Correct 7 ms 1408 KB Output is correct
37 Correct 8 ms 1536 KB Output is correct
38 Correct 7 ms 1408 KB Output is correct
39 Correct 7 ms 1280 KB Output is correct
40 Correct 7 ms 1280 KB Output is correct
41 Correct 7 ms 1408 KB Output is correct
42 Correct 8 ms 1408 KB Output is correct
43 Correct 7 ms 1280 KB Output is correct
44 Correct 7 ms 1280 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 8 ms 1408 KB Output is correct
26 Correct 8 ms 1408 KB Output is correct
27 Correct 8 ms 1408 KB Output is correct
28 Correct 7 ms 1408 KB Output is correct
29 Correct 8 ms 1408 KB Output is correct
30 Correct 8 ms 1408 KB Output is correct
31 Correct 8 ms 1408 KB Output is correct
32 Correct 8 ms 1408 KB Output is correct
33 Correct 8 ms 1328 KB Output is correct
34 Correct 7 ms 1408 KB Output is correct
35 Correct 7 ms 1280 KB Output is correct
36 Correct 7 ms 1408 KB Output is correct
37 Correct 8 ms 1536 KB Output is correct
38 Correct 7 ms 1408 KB Output is correct
39 Correct 7 ms 1280 KB Output is correct
40 Correct 7 ms 1280 KB Output is correct
41 Correct 7 ms 1408 KB Output is correct
42 Correct 8 ms 1408 KB Output is correct
43 Correct 7 ms 1280 KB Output is correct
44 Correct 7 ms 1280 KB Output is correct
45 Correct 200 ms 59640 KB Output is correct
46 Correct 200 ms 59640 KB Output is correct
47 Correct 195 ms 59640 KB Output is correct
48 Correct 198 ms 59768 KB Output is correct
49 Correct 200 ms 59756 KB Output is correct
50 Correct 205 ms 59256 KB Output is correct
51 Correct 197 ms 59384 KB Output is correct
52 Correct 140 ms 53408 KB Output is correct
53 Correct 190 ms 64888 KB Output is correct
54 Correct 187 ms 65400 KB Output is correct
55 Correct 187 ms 64300 KB Output is correct
56 Correct 186 ms 64120 KB Output is correct
57 Correct 139 ms 53884 KB Output is correct
58 Correct 147 ms 53496 KB Output is correct
59 Correct 189 ms 57344 KB Output is correct
60 Correct 188 ms 57336 KB Output is correct
61 Correct 190 ms 57592 KB Output is correct
62 Correct 184 ms 57336 KB Output is correct
63 Correct 186 ms 56824 KB Output is correct
64 Correct 189 ms 57208 KB Output is correct
65 Correct 288 ms 64200 KB Output is correct
66 Correct 284 ms 64068 KB Output is correct
67 Correct 200 ms 64248 KB Output is correct
68 Correct 203 ms 64376 KB Output is correct
69 Correct 201 ms 64248 KB Output is correct
70 Correct 202 ms 64248 KB Output is correct
71 Correct 195 ms 65492 KB Output is correct
72 Correct 193 ms 65400 KB Output is correct
73 Correct 194 ms 65400 KB Output is correct
74 Correct 197 ms 65560 KB Output is correct
75 Correct 139 ms 53752 KB Output is correct
76 Correct 146 ms 53752 KB Output is correct
77 Correct 145 ms 53496 KB Output is correct
78 Correct 207 ms 59768 KB Output is correct
79 Correct 199 ms 59640 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 8 ms 1408 KB Output is correct
26 Correct 8 ms 1408 KB Output is correct
27 Correct 8 ms 1408 KB Output is correct
28 Correct 7 ms 1408 KB Output is correct
29 Correct 8 ms 1408 KB Output is correct
30 Correct 8 ms 1408 KB Output is correct
31 Correct 8 ms 1408 KB Output is correct
32 Correct 8 ms 1408 KB Output is correct
33 Correct 8 ms 1328 KB Output is correct
34 Correct 7 ms 1408 KB Output is correct
35 Correct 7 ms 1280 KB Output is correct
36 Correct 7 ms 1408 KB Output is correct
37 Correct 8 ms 1536 KB Output is correct
38 Correct 7 ms 1408 KB Output is correct
39 Correct 7 ms 1280 KB Output is correct
40 Correct 7 ms 1280 KB Output is correct
41 Correct 7 ms 1408 KB Output is correct
42 Correct 8 ms 1408 KB Output is correct
43 Correct 7 ms 1280 KB Output is correct
44 Correct 7 ms 1280 KB Output is correct
45 Correct 200 ms 59640 KB Output is correct
46 Correct 200 ms 59640 KB Output is correct
47 Correct 195 ms 59640 KB Output is correct
48 Correct 198 ms 59768 KB Output is correct
49 Correct 200 ms 59756 KB Output is correct
50 Correct 205 ms 59256 KB Output is correct
51 Correct 197 ms 59384 KB Output is correct
52 Correct 140 ms 53408 KB Output is correct
53 Correct 190 ms 64888 KB Output is correct
54 Correct 187 ms 65400 KB Output is correct
55 Correct 187 ms 64300 KB Output is correct
56 Correct 186 ms 64120 KB Output is correct
57 Correct 139 ms 53884 KB Output is correct
58 Correct 147 ms 53496 KB Output is correct
59 Correct 189 ms 57344 KB Output is correct
60 Correct 188 ms 57336 KB Output is correct
61 Correct 190 ms 57592 KB Output is correct
62 Correct 184 ms 57336 KB Output is correct
63 Correct 186 ms 56824 KB Output is correct
64 Correct 189 ms 57208 KB Output is correct
65 Correct 288 ms 64200 KB Output is correct
66 Correct 284 ms 64068 KB Output is correct
67 Correct 200 ms 64248 KB Output is correct
68 Correct 203 ms 64376 KB Output is correct
69 Correct 201 ms 64248 KB Output is correct
70 Correct 202 ms 64248 KB Output is correct
71 Correct 195 ms 65492 KB Output is correct
72 Correct 193 ms 65400 KB Output is correct
73 Correct 194 ms 65400 KB Output is correct
74 Correct 197 ms 65560 KB Output is correct
75 Correct 139 ms 53752 KB Output is correct
76 Correct 146 ms 53752 KB Output is correct
77 Correct 145 ms 53496 KB Output is correct
78 Correct 207 ms 59768 KB Output is correct
79 Correct 199 ms 59640 KB Output is correct
80 Correct 2172 ms 610836 KB Output is correct
81 Correct 2085 ms 610564 KB Output is correct
82 Correct 2100 ms 610484 KB Output is correct
83 Correct 2100 ms 610700 KB Output is correct
84 Correct 2150 ms 610316 KB Output is correct
85 Correct 2158 ms 607528 KB Output is correct
86 Correct 2093 ms 608672 KB Output is correct
87 Correct 1403 ms 534648 KB Output is correct
88 Correct 2089 ms 678124 KB Output is correct
89 Correct 2021 ms 682048 KB Output is correct
90 Correct 2016 ms 670260 KB Output is correct
91 Correct 1985 ms 670280 KB Output is correct
92 Correct 1415 ms 538744 KB Output is correct
93 Correct 1458 ms 534748 KB Output is correct
94 Correct 1923 ms 580344 KB Output is correct
95 Correct 1989 ms 584572 KB Output is correct
96 Correct 1989 ms 590732 KB Output is correct
97 Correct 1898 ms 577520 KB Output is correct
98 Correct 1976 ms 582660 KB Output is correct
99 Correct 2017 ms 586804 KB Output is correct
100 Correct 3866 ms 668196 KB Output is correct
101 Correct 3951 ms 668268 KB Output is correct
102 Correct 2139 ms 670192 KB Output is correct
103 Correct 2175 ms 669984 KB Output is correct
104 Correct 2122 ms 669604 KB Output is correct
105 Correct 2159 ms 669704 KB Output is correct
106 Correct 2061 ms 682184 KB Output is correct
107 Correct 2029 ms 682188 KB Output is correct
108 Correct 2122 ms 682084 KB Output is correct
109 Correct 2037 ms 682184 KB Output is correct
110 Correct 1427 ms 538492 KB Output is correct
111 Correct 1488 ms 538480 KB Output is correct
112 Correct 1477 ms 536440 KB Output is correct
113 Correct 2065 ms 610808 KB Output is correct
114 Correct 2086 ms 610596 KB Output is correct