oj.uz

답안 #132185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132185 2019-07-18T12:09:04 Z IC_COLDSTOP Port Facility (JOI17_port_facility) C++17
100 / 100
 2948 ms 522352 KB 
#include<bits/stdc++.h>
using namespace std;
ofstream fout ("out.txt");
#define ll long long
//#define int ll
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define pii pair<int,int>
#define REP(i,a,b) for(int i=a; i<b; i++)

const int MX=2e6+3, mod=1e9+7;

int n, cnt[MX], ans=1, par[MX], cl[MX];
pii arr[MX];
set<pii> vec[MX], veccl[2][MX];

int parent(int u){ return par[u]<0 ? u : par[u]=parent(par[u]); }

void join(int u, int v){
    int a=cl[u], b=cl[v];
    if((parent(u))==(parent(v))){
        //cout<<u<<" "<<v<<" "<<a<<" "<<b<<endl;
        if(a==b){
            cout<<0<<endl;
            exit(0);
        }
        return;
    }
    u=parent(u), v=parent(v);
    if(par[u]>par[v]) swap(u,v);
    for(auto w:vec[v]){
        vec[u].insert(w);
        if(a==b) cl[w.S]^=1;
        if(cl[w.S]) veccl[1][u].insert(w);
        else veccl[0][u].insert(w);
    }
    par[u]+=par[v];
    par[v]=u;
}

int32_t main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(par, -1,sizeof par);
    cin>>n;
    REP(i,0,n) cin>>arr[i].F>>arr[i].S;
    sort(arr, arr+n);
    set<pii> st;
    REP(i,0,n){
        //cout<<i<<endl;
        int a=arr[i].F, b=arr[i].S;
        vec[i].insert(MP(b,i));
        veccl[0][i].insert(MP(b,i));
        while(st.size() && (*st.begin()).F<a){
            auto u=(*st.begin());
            int cur=parent(u.S);
            vec[cur].erase(vec[cur].begin());
            if(!vec[cur].size()){
                ans=ans*2%mod;
                //cout<<cur<<" "<<par[cur]<<endl;
            }
            else st.insert((*vec[cur].begin()));
            st.erase(st.begin());
        }
        //cout<<i<<endl;
        while(st.size() && (*st.begin()).F<b){
            auto u=(*st.begin());
            join(u.S, i);
            st.erase(u);
        }
        int cur=parent(i), l=cl[(*vec[cur].begin()).S];
        st.insert((*vec[cur].begin()));
        auto u=veccl[l^1][cur].lower_bound(MP(a,0));
        if(u!=veccl[l^1][cur].end()) st.insert((*u));
        /*for(auto u:vec[cur]){
            if(u==(*vec[cur].begin())) continue;
            if(cl[u.S]!=l){
                st.insert(u);
                break;
            }
        }*/
    }
    while(st.size()){
        auto u=(*st.begin());
        int cur=parent(u.S);
        vec[cur].erase(vec[cur].begin());
        if(!vec[cur].size()){
            ans=ans*2%mod;
            //cout<<cur<<" "<<par[cur]<<endl;
        }
        else st.insert((*vec[cur].begin()));
        st.erase(st.begin());
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 290040 KB Output is correct
2 Correct 264 ms 290040 KB Output is correct
3 Correct 261 ms 290052 KB Output is correct
4 Correct 263 ms 290028 KB Output is correct
5 Correct 272 ms 290168 KB Output is correct
6 Correct 263 ms 290040 KB Output is correct
7 Correct 269 ms 290040 KB Output is correct
8 Correct 276 ms 290032 KB Output is correct
9 Correct 266 ms 290040 KB Output is correct
10 Correct 280 ms 290040 KB Output is correct
11 Correct 263 ms 290052 KB Output is correct
12 Correct 261 ms 290164 KB Output is correct
13 Correct 263 ms 290180 KB Output is correct
14 Correct 262 ms 290256 KB Output is correct
15 Correct 262 ms 290040 KB Output is correct
16 Correct 265 ms 290068 KB Output is correct
17 Correct 263 ms 290096 KB Output is correct
18 Correct 263 ms 289916 KB Output is correct
19 Correct 265 ms 289912 KB Output is correct
20 Correct 268 ms 290040 KB Output is correct
21 Correct 281 ms 289948 KB Output is correct
22 Correct 264 ms 289916 KB Output is correct
23 Correct 309 ms 290040 KB Output is correct
24 Correct 264 ms 289912 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 290040 KB Output is correct
2 Correct 264 ms 290040 KB Output is correct
3 Correct 261 ms 290052 KB Output is correct
4 Correct 263 ms 290028 KB Output is correct
5 Correct 272 ms 290168 KB Output is correct
6 Correct 263 ms 290040 KB Output is correct
7 Correct 269 ms 290040 KB Output is correct
8 Correct 276 ms 290032 KB Output is correct
9 Correct 266 ms 290040 KB Output is correct
10 Correct 280 ms 290040 KB Output is correct
11 Correct 263 ms 290052 KB Output is correct
12 Correct 261 ms 290164 KB Output is correct
13 Correct 263 ms 290180 KB Output is correct
14 Correct 262 ms 290256 KB Output is correct
15 Correct 262 ms 290040 KB Output is correct
16 Correct 265 ms 290068 KB Output is correct
17 Correct 263 ms 290096 KB Output is correct
18 Correct 263 ms 289916 KB Output is correct
19 Correct 265 ms 289912 KB Output is correct
20 Correct 268 ms 290040 KB Output is correct
21 Correct 281 ms 289948 KB Output is correct
22 Correct 264 ms 289916 KB Output is correct
23 Correct 309 ms 290040 KB Output is correct
24 Correct 264 ms 289912 KB Output is correct
25 Correct 268 ms 290536 KB Output is correct
26 Correct 267 ms 290312 KB Output is correct
27 Correct 267 ms 290296 KB Output is correct
28 Correct 265 ms 290444 KB Output is correct
29 Correct 263 ms 290296 KB Output is correct
30 Correct 266 ms 290296 KB Output is correct
31 Correct 270 ms 290408 KB Output is correct
32 Correct 273 ms 290392 KB Output is correct
33 Correct 277 ms 290296 KB Output is correct
34 Correct 272 ms 290204 KB Output is correct
35 Correct 267 ms 290104 KB Output is correct
36 Correct 269 ms 290424 KB Output is correct
37 Correct 266 ms 290032 KB Output is correct
38 Correct 275 ms 290020 KB Output is correct
39 Correct 273 ms 290296 KB Output is correct
40 Correct 265 ms 290132 KB Output is correct
41 Correct 313 ms 290460 KB Output is correct
42 Correct 314 ms 290428 KB Output is correct
43 Correct 276 ms 290388 KB Output is correct
44 Correct 265 ms 290340 KB Output is correct

Subtask #3
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 290040 KB Output is correct
2 Correct 264 ms 290040 KB Output is correct
3 Correct 261 ms 290052 KB Output is correct
4 Correct 263 ms 290028 KB Output is correct
5 Correct 272 ms 290168 KB Output is correct
6 Correct 263 ms 290040 KB Output is correct
7 Correct 269 ms 290040 KB Output is correct
8 Correct 276 ms 290032 KB Output is correct
9 Correct 266 ms 290040 KB Output is correct
10 Correct 280 ms 290040 KB Output is correct
11 Correct 263 ms 290052 KB Output is correct
12 Correct 261 ms 290164 KB Output is correct
13 Correct 263 ms 290180 KB Output is correct
14 Correct 262 ms 290256 KB Output is correct
15 Correct 262 ms 290040 KB Output is correct
16 Correct 265 ms 290068 KB Output is correct
17 Correct 263 ms 290096 KB Output is correct
18 Correct 263 ms 289916 KB Output is correct
19 Correct 265 ms 289912 KB Output is correct
20 Correct 268 ms 290040 KB Output is correct
21 Correct 281 ms 289948 KB Output is correct
22 Correct 264 ms 289916 KB Output is correct
23 Correct 309 ms 290040 KB Output is correct
24 Correct 264 ms 289912 KB Output is correct
25 Correct 268 ms 290536 KB Output is correct
26 Correct 267 ms 290312 KB Output is correct
27 Correct 267 ms 290296 KB Output is correct
28 Correct 265 ms 290444 KB Output is correct
29 Correct 263 ms 290296 KB Output is correct
30 Correct 266 ms 290296 KB Output is correct
31 Correct 270 ms 290408 KB Output is correct
32 Correct 273 ms 290392 KB Output is correct
33 Correct 277 ms 290296 KB Output is correct
34 Correct 272 ms 290204 KB Output is correct
35 Correct 267 ms 290104 KB Output is correct
36 Correct 269 ms 290424 KB Output is correct
37 Correct 266 ms 290032 KB Output is correct
38 Correct 275 ms 290020 KB Output is correct
39 Correct 273 ms 290296 KB Output is correct
40 Correct 265 ms 290132 KB Output is correct
41 Correct 313 ms 290460 KB Output is correct
42 Correct 314 ms 290428 KB Output is correct
43 Correct 276 ms 290388 KB Output is correct
44 Correct 265 ms 290340 KB Output is correct
45 Correct 417 ms 308588 KB Output is correct
46 Correct 452 ms 308444 KB Output is correct
47 Correct 451 ms 308728 KB Output is correct
48 Correct 442 ms 308364 KB Output is correct
49 Correct 482 ms 308772 KB Output is correct
50 Correct 322 ms 296312 KB Output is correct
51 Correct 354 ms 301216 KB Output is correct
52 Correct 315 ms 295468 KB Output is correct
53 Correct 345 ms 305044 KB Output is correct
54 Correct 292 ms 290808 KB Output is correct
55 Correct 294 ms 290832 KB Output is correct
56 Correct 295 ms 290808 KB Output is correct
57 Correct 332 ms 300692 KB Output is correct
58 Correct 318 ms 295492 KB Output is correct
59 Correct 333 ms 297932 KB Output is correct
60 Correct 361 ms 300520 KB Output is correct
61 Correct 423 ms 304460 KB Output is correct
62 Correct 308 ms 290936 KB Output is correct
63 Correct 292 ms 290808 KB Output is correct
64 Correct 301 ms 291060 KB Output is correct
65 Correct 296 ms 290812 KB Output is correct
66 Correct 296 ms 290888 KB Output is correct
67 Correct 425 ms 309760 KB Output is correct
68 Correct 431 ms 311032 KB Output is correct
69 Correct 432 ms 312752 KB Output is correct
70 Correct 419 ms 312688 KB Output is correct
71 Correct 450 ms 313528 KB Output is correct
72 Correct 447 ms 313464 KB Output is correct
73 Correct 461 ms 314360 KB Output is correct
74 Correct 465 ms 314328 KB Output is correct
75 Correct 385 ms 306552 KB Output is correct
76 Correct 393 ms 306452 KB Output is correct
77 Correct 399 ms 306552 KB Output is correct
78 Correct 420 ms 309800 KB Output is correct
79 Correct 415 ms 309688 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 290040 KB Output is correct
2 Correct 264 ms 290040 KB Output is correct
3 Correct 261 ms 290052 KB Output is correct
4 Correct 263 ms 290028 KB Output is correct
5 Correct 272 ms 290168 KB Output is correct
6 Correct 263 ms 290040 KB Output is correct
7 Correct 269 ms 290040 KB Output is correct
8 Correct 276 ms 290032 KB Output is correct
9 Correct 266 ms 290040 KB Output is correct
10 Correct 280 ms 290040 KB Output is correct
11 Correct 263 ms 290052 KB Output is correct
12 Correct 261 ms 290164 KB Output is correct
13 Correct 263 ms 290180 KB Output is correct
14 Correct 262 ms 290256 KB Output is correct
15 Correct 262 ms 290040 KB Output is correct
16 Correct 265 ms 290068 KB Output is correct
17 Correct 263 ms 290096 KB Output is correct
18 Correct 263 ms 289916 KB Output is correct
19 Correct 265 ms 289912 KB Output is correct
20 Correct 268 ms 290040 KB Output is correct
21 Correct 281 ms 289948 KB Output is correct
22 Correct 264 ms 289916 KB Output is correct
23 Correct 309 ms 290040 KB Output is correct
24 Correct 264 ms 289912 KB Output is correct
25 Correct 268 ms 290536 KB Output is correct
26 Correct 267 ms 290312 KB Output is correct
27 Correct 267 ms 290296 KB Output is correct
28 Correct 265 ms 290444 KB Output is correct
29 Correct 263 ms 290296 KB Output is correct
30 Correct 266 ms 290296 KB Output is correct
31 Correct 270 ms 290408 KB Output is correct
32 Correct 273 ms 290392 KB Output is correct
33 Correct 277 ms 290296 KB Output is correct
34 Correct 272 ms 290204 KB Output is correct
35 Correct 267 ms 290104 KB Output is correct
36 Correct 269 ms 290424 KB Output is correct
37 Correct 266 ms 290032 KB Output is correct
38 Correct 275 ms 290020 KB Output is correct
39 Correct 273 ms 290296 KB Output is correct
40 Correct 265 ms 290132 KB Output is correct
41 Correct 313 ms 290460 KB Output is correct
42 Correct 314 ms 290428 KB Output is correct
43 Correct 276 ms 290388 KB Output is correct
44 Correct 265 ms 290340 KB Output is correct
45 Correct 417 ms 308588 KB Output is correct
46 Correct 452 ms 308444 KB Output is correct
47 Correct 451 ms 308728 KB Output is correct
48 Correct 442 ms 308364 KB Output is correct
49 Correct 482 ms 308772 KB Output is correct
50 Correct 322 ms 296312 KB Output is correct
51 Correct 354 ms 301216 KB Output is correct
52 Correct 315 ms 295468 KB Output is correct
53 Correct 345 ms 305044 KB Output is correct
54 Correct 292 ms 290808 KB Output is correct
55 Correct 294 ms 290832 KB Output is correct
56 Correct 295 ms 290808 KB Output is correct
57 Correct 332 ms 300692 KB Output is correct
58 Correct 318 ms 295492 KB Output is correct
59 Correct 333 ms 297932 KB Output is correct
60 Correct 361 ms 300520 KB Output is correct
61 Correct 423 ms 304460 KB Output is correct
62 Correct 308 ms 290936 KB Output is correct
63 Correct 292 ms 290808 KB Output is correct
64 Correct 301 ms 291060 KB Output is correct
65 Correct 296 ms 290812 KB Output is correct
66 Correct 296 ms 290888 KB Output is correct
67 Correct 425 ms 309760 KB Output is correct
68 Correct 431 ms 311032 KB Output is correct
69 Correct 432 ms 312752 KB Output is correct
70 Correct 419 ms 312688 KB Output is correct
71 Correct 450 ms 313528 KB Output is correct
72 Correct 447 ms 313464 KB Output is correct
73 Correct 461 ms 314360 KB Output is correct
74 Correct 465 ms 314328 KB Output is correct
75 Correct 385 ms 306552 KB Output is correct
76 Correct 393 ms 306452 KB Output is correct
77 Correct 399 ms 306552 KB Output is correct
78 Correct 420 ms 309800 KB Output is correct
79 Correct 415 ms 309688 KB Output is correct
80 Correct 2043 ms 479832 KB Output is correct
81 Correct 1991 ms 477860 KB Output is correct
82 Correct 1898 ms 478456 KB Output is correct
83 Correct 2013 ms 478340 KB Output is correct
84 Correct 2019 ms 478500 KB Output is correct
85 Correct 1113 ms 394748 KB Output is correct
86 Correct 1328 ms 422600 KB Output is correct
87 Correct 838 ms 348392 KB Output is correct
88 Correct 1264 ms 442312 KB Output is correct
89 Correct 603 ms 301480 KB Output is correct
90 Correct 615 ms 301400 KB Output is correct
91 Correct 619 ms 301484 KB Output is correct
92 Correct 998 ms 399204 KB Output is correct
93 Correct 832 ms 348372 KB Output is correct
94 Correct 1131 ms 380428 KB Output is correct
95 Correct 1578 ms 427548 KB Output is correct
96 Correct 1777 ms 452424 KB Output is correct
97 Correct 747 ms 333304 KB Output is correct
98 Correct 973 ms 370020 KB Output is correct
99 Correct 819 ms 327884 KB Output is correct
100 Correct 616 ms 301420 KB Output is correct
101 Correct 641 ms 300892 KB Output is correct
102 Correct 2281 ms 490508 KB Output is correct
103 Correct 2364 ms 490376 KB Output is correct
104 Correct 2179 ms 506748 KB Output is correct
105 Correct 2191 ms 506808 KB Output is correct
106 Correct 2815 ms 513824 KB Output is correct
107 Correct 2760 ms 513732 KB Output is correct
108 Correct 2935 ms 522160 KB Output is correct
109 Correct 2948 ms 522352 KB Output is correct
110 Correct 1717 ms 445080 KB Output is correct
111 Correct 1817 ms 444888 KB Output is correct
112 Correct 1881 ms 444948 KB Output is correct
113 Correct 1876 ms 477116 KB Output is correct
114 Correct 1970 ms 476280 KB Output is correct