oj.uz

답안 #800189

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
800189 2023-08-01T11:28:02 Z vjudge1 Port Facility (JOI17_port_facility) C++
78 / 100
 6000 ms 157056 KB 
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const int N = (1 << 21), mod = 1e9 + 7 ;
bool flag, us[N + 1] ;
int n, cnt, color[N + 1], a[N + 1], b[N + 1] ;
pair<int, int> mn[2 * N + 1], mx[2 * N + 1] ;
int binpow(ll num, ll pw)
{
    ll res = 1 ;
    while(pw)
        if(pw & 1)
        {
            res *= num ;
            pw ^= 1 ;
            res %= mod ;
        }
        else
        {
            num *= num ;
            pw >>= 1 ;
            num %= mod ;
        }
    return res ;
}
void build(int l, int r, int v)
{
    if(l == r)
    {
        mx[v] = {-1e9, l} ;
        mn[v] = {1e9, l} ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(l, mid, v * 2) ;
    build(mid + 1, r, v * 2 + 1) ;
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]) ;
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]) ;
}
void update_min(int l, int r, int pos, pair<int, int> p, int v)
{
    if(l > pos || r < pos)
        return ;
    if(l == r)
    {
        mn[v] = p ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    update_min(l, mid, pos, p, v * 2) ;
    update_min(mid + 1, r, pos, p, v * 2 + 1) ;
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]) ;
}
void update_max(int l, int r, int pos, pair<int, int> p, int v)
{
    if(l > pos || r < pos)
        return ;
    if(l == r)
    {
        mx[v] = p ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    update_max(l, mid, pos, p, v * 2) ;
    update_max(mid + 1, r, pos, p, v * 2 + 1) ;
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]) ;
}
pair<int, int> get_max(int l, int r, int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return {-1e9, 0} ;
    if(l1 <= l && r <= r1)
        return mx[v] ;
    int mid = (l + r) >> 1 ;
    pair<int, int> p1 = get_max(l, mid, l1, r1, v * 2), p2 = get_max(mid + 1, r, l1, r1, v * 2 + 1) ;
    return max(p1, p2) ;
}
pair<int, int> get_min(int l, int r, int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return {1e9, 0} ;
    if(l1 <= l && r <= r1)
        return mn[v] ;
    int mid = (l + r) >> 1 ;
    pair<int, int> p1 = get_min(l, mid, l1, r1, v * 2), p2 = get_min(mid + 1, r, l1, r1, v * 2 + 1) ;
    return min(p1, p2) ;
}
void dfs(int city)
{
    bool abu = 1 ;
    us[city] = 1 ;
    update_max(1, N, a[city], {-1e9, city}, 1) ;
    update_min(1, N, b[city], {1e9, city}, 1) ;
    while(abu)
    {
        abu ^= 1 ;
        pair<int, int> lf = get_min(1, N, a[city], b[city], 1), rg = get_max(1, N, a[city], b[city], 1) ;
        if(lf.fi < a[city])
        {
            color[lf.se] = (1 ^ color[city]) ;
            dfs(lf.se) ;
            abu = 1 ;
        }
        if(rg.fi > b[city])
        {
            color[rg.se] = (1 ^ color[city]) ;
            dfs(rg.se) ;
            abu = 1 ;
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    build(1, N, 1) ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i] >> b[i] ;
        update_min(1, N, b[i], {a[i], i}, 1) ;
        update_max(1, N, a[i], {b[i], i}, 1) ;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(us[i])
            continue ;
        cnt++ ;
        dfs(i) ;
    }
    for(int j = 0 ; j < 2 ; j++)
    {
        build(1, N, 1) ;
        for(int i = 1 ; i <= n ; i++)
            if(color[i] == j)
            {
                update_min(1, N, b[i], {a[i], i}, 1) ;
                update_max(1, N, a[i], {b[i], i}, 1) ;
            }
        for(int i = 1 ; i <= n ; i++)
        {
            if(color[i] != j)
                continue ;
            pair<int, int> lf = get_min(1, N, a[i], b[i], 1), rg = get_max(1, N, a[i], b[i], 1) ;
            if(lf.fi < a[i] || rg.fi > b[i])flag = 1 ;
        }
    }
    if(flag)
        cout << "0\n" ;
    else
        cout << binpow(2, cnt) ;
    return 0 ;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 65912 KB Output is correct
2 Correct 72 ms 65996 KB Output is correct
3 Correct 68 ms 65904 KB Output is correct
4 Correct 68 ms 66004 KB Output is correct
5 Correct 67 ms 65868 KB Output is correct
6 Correct 72 ms 65904 KB Output is correct
7 Correct 68 ms 66004 KB Output is correct
8 Correct 68 ms 65988 KB Output is correct
9 Correct 68 ms 65996 KB Output is correct
10 Correct 69 ms 65988 KB Output is correct
11 Correct 69 ms 65996 KB Output is correct
12 Correct 70 ms 65896 KB Output is correct
13 Correct 73 ms 65988 KB Output is correct
14 Correct 71 ms 65988 KB Output is correct
15 Correct 69 ms 65980 KB Output is correct
16 Correct 70 ms 65996 KB Output is correct
17 Correct 80 ms 65956 KB Output is correct
18 Correct 70 ms 65984 KB Output is correct
19 Correct 69 ms 65980 KB Output is correct
20 Correct 72 ms 65932 KB Output is correct
21 Correct 71 ms 66004 KB Output is correct
22 Correct 69 ms 65868 KB Output is correct
23 Correct 69 ms 65996 KB Output is correct
24 Correct 69 ms 65932 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 65912 KB Output is correct
2 Correct 72 ms 65996 KB Output is correct
3 Correct 68 ms 65904 KB Output is correct
4 Correct 68 ms 66004 KB Output is correct
5 Correct 67 ms 65868 KB Output is correct
6 Correct 72 ms 65904 KB Output is correct
7 Correct 68 ms 66004 KB Output is correct
8 Correct 68 ms 65988 KB Output is correct
9 Correct 68 ms 65996 KB Output is correct
10 Correct 69 ms 65988 KB Output is correct
11 Correct 69 ms 65996 KB Output is correct
12 Correct 70 ms 65896 KB Output is correct
13 Correct 73 ms 65988 KB Output is correct
14 Correct 71 ms 65988 KB Output is correct
15 Correct 69 ms 65980 KB Output is correct
16 Correct 70 ms 65996 KB Output is correct
17 Correct 80 ms 65956 KB Output is correct
18 Correct 70 ms 65984 KB Output is correct
19 Correct 69 ms 65980 KB Output is correct
20 Correct 72 ms 65932 KB Output is correct
21 Correct 71 ms 66004 KB Output is correct
22 Correct 69 ms 65868 KB Output is correct
23 Correct 69 ms 65996 KB Output is correct
24 Correct 69 ms 65932 KB Output is correct
25 Correct 76 ms 65996 KB Output is correct
26 Correct 73 ms 65980 KB Output is correct
27 Correct 74 ms 66080 KB Output is correct
28 Correct 78 ms 66076 KB Output is correct
29 Correct 91 ms 66004 KB Output is correct
30 Correct 82 ms 66096 KB Output is correct
31 Correct 74 ms 66004 KB Output is correct
32 Correct 74 ms 66004 KB Output is correct
33 Correct 78 ms 66136 KB Output is correct
34 Correct 74 ms 66064 KB Output is correct
35 Correct 73 ms 66004 KB Output is correct
36 Correct 74 ms 66008 KB Output is correct
37 Correct 77 ms 66084 KB Output is correct
38 Correct 74 ms 66080 KB Output is correct
39 Correct 75 ms 65960 KB Output is correct
40 Correct 72 ms 65996 KB Output is correct
41 Correct 72 ms 66112 KB Output is correct
42 Correct 74 ms 66132 KB Output is correct
43 Correct 72 ms 66172 KB Output is correct
44 Correct 77 ms 66128 KB Output is correct

Subtask #3
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 65912 KB Output is correct
2 Correct 72 ms 65996 KB Output is correct
3 Correct 68 ms 65904 KB Output is correct
4 Correct 68 ms 66004 KB Output is correct
5 Correct 67 ms 65868 KB Output is correct
6 Correct 72 ms 65904 KB Output is correct
7 Correct 68 ms 66004 KB Output is correct
8 Correct 68 ms 65988 KB Output is correct
9 Correct 68 ms 65996 KB Output is correct
10 Correct 69 ms 65988 KB Output is correct
11 Correct 69 ms 65996 KB Output is correct
12 Correct 70 ms 65896 KB Output is correct
13 Correct 73 ms 65988 KB Output is correct
14 Correct 71 ms 65988 KB Output is correct
15 Correct 69 ms 65980 KB Output is correct
16 Correct 70 ms 65996 KB Output is correct
17 Correct 80 ms 65956 KB Output is correct
18 Correct 70 ms 65984 KB Output is correct
19 Correct 69 ms 65980 KB Output is correct
20 Correct 72 ms 65932 KB Output is correct
21 Correct 71 ms 66004 KB Output is correct
22 Correct 69 ms 65868 KB Output is correct
23 Correct 69 ms 65996 KB Output is correct
24 Correct 69 ms 65932 KB Output is correct
25 Correct 76 ms 65996 KB Output is correct
26 Correct 73 ms 65980 KB Output is correct
27 Correct 74 ms 66080 KB Output is correct
28 Correct 78 ms 66076 KB Output is correct
29 Correct 91 ms 66004 KB Output is correct
30 Correct 82 ms 66096 KB Output is correct
31 Correct 74 ms 66004 KB Output is correct
32 Correct 74 ms 66004 KB Output is correct
33 Correct 78 ms 66136 KB Output is correct
34 Correct 74 ms 66064 KB Output is correct
35 Correct 73 ms 66004 KB Output is correct
36 Correct 74 ms 66008 KB Output is correct
37 Correct 77 ms 66084 KB Output is correct
38 Correct 74 ms 66080 KB Output is correct
39 Correct 75 ms 65960 KB Output is correct
40 Correct 72 ms 65996 KB Output is correct
41 Correct 72 ms 66112 KB Output is correct
42 Correct 74 ms 66132 KB Output is correct
43 Correct 72 ms 66172 KB Output is correct
44 Correct 77 ms 66128 KB Output is correct
45 Correct 381 ms 68392 KB Output is correct
46 Correct 382 ms 69424 KB Output is correct
47 Correct 387 ms 67668 KB Output is correct
48 Correct 376 ms 69396 KB Output is correct
49 Correct 394 ms 67920 KB Output is correct
50 Correct 386 ms 69136 KB Output is correct
51 Correct 392 ms 69160 KB Output is correct
52 Correct 279 ms 66812 KB Output is correct
53 Correct 378 ms 66992 KB Output is correct
54 Correct 380 ms 75080 KB Output is correct
55 Correct 386 ms 71292 KB Output is correct
56 Correct 381 ms 71096 KB Output is correct
57 Correct 317 ms 67284 KB Output is correct
58 Correct 320 ms 66884 KB Output is correct
59 Correct 333 ms 67280 KB Output is correct
60 Correct 360 ms 67280 KB Output is correct
61 Correct 414 ms 67276 KB Output is correct
62 Correct 347 ms 67276 KB Output is correct
63 Correct 371 ms 67184 KB Output is correct
64 Correct 372 ms 67280 KB Output is correct
65 Correct 519 ms 75104 KB Output is correct
66 Correct 521 ms 75104 KB Output is correct
67 Correct 393 ms 71228 KB Output is correct
68 Correct 383 ms 71116 KB Output is correct
69 Correct 389 ms 70760 KB Output is correct
70 Correct 394 ms 70744 KB Output is correct
71 Correct 380 ms 75100 KB Output is correct
72 Correct 388 ms 75100 KB Output is correct
73 Correct 381 ms 72492 KB Output is correct
74 Correct 376 ms 72396 KB Output is correct
75 Correct 317 ms 71900 KB Output is correct
76 Correct 306 ms 75088 KB Output is correct
77 Correct 312 ms 75216 KB Output is correct
78 Correct 387 ms 69176 KB Output is correct
79 Correct 415 ms 68540 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 65912 KB Output is correct
2 Correct 72 ms 65996 KB Output is correct
3 Correct 68 ms 65904 KB Output is correct
4 Correct 68 ms 66004 KB Output is correct
5 Correct 67 ms 65868 KB Output is correct
6 Correct 72 ms 65904 KB Output is correct
7 Correct 68 ms 66004 KB Output is correct
8 Correct 68 ms 65988 KB Output is correct
9 Correct 68 ms 65996 KB Output is correct
10 Correct 69 ms 65988 KB Output is correct
11 Correct 69 ms 65996 KB Output is correct
12 Correct 70 ms 65896 KB Output is correct
13 Correct 73 ms 65988 KB Output is correct
14 Correct 71 ms 65988 KB Output is correct
15 Correct 69 ms 65980 KB Output is correct
16 Correct 70 ms 65996 KB Output is correct
17 Correct 80 ms 65956 KB Output is correct
18 Correct 70 ms 65984 KB Output is correct
19 Correct 69 ms 65980 KB Output is correct
20 Correct 72 ms 65932 KB Output is correct
21 Correct 71 ms 66004 KB Output is correct
22 Correct 69 ms 65868 KB Output is correct
23 Correct 69 ms 65996 KB Output is correct
24 Correct 69 ms 65932 KB Output is correct
25 Correct 76 ms 65996 KB Output is correct
26 Correct 73 ms 65980 KB Output is correct
27 Correct 74 ms 66080 KB Output is correct
28 Correct 78 ms 66076 KB Output is correct
29 Correct 91 ms 66004 KB Output is correct
30 Correct 82 ms 66096 KB Output is correct
31 Correct 74 ms 66004 KB Output is correct
32 Correct 74 ms 66004 KB Output is correct
33 Correct 78 ms 66136 KB Output is correct
34 Correct 74 ms 66064 KB Output is correct
35 Correct 73 ms 66004 KB Output is correct
36 Correct 74 ms 66008 KB Output is correct
37 Correct 77 ms 66084 KB Output is correct
38 Correct 74 ms 66080 KB Output is correct
39 Correct 75 ms 65960 KB Output is correct
40 Correct 72 ms 65996 KB Output is correct
41 Correct 72 ms 66112 KB Output is correct
42 Correct 74 ms 66132 KB Output is correct
43 Correct 72 ms 66172 KB Output is correct
44 Correct 77 ms 66128 KB Output is correct
45 Correct 381 ms 68392 KB Output is correct
46 Correct 382 ms 69424 KB Output is correct
47 Correct 387 ms 67668 KB Output is correct
48 Correct 376 ms 69396 KB Output is correct
49 Correct 394 ms 67920 KB Output is correct
50 Correct 386 ms 69136 KB Output is correct
51 Correct 392 ms 69160 KB Output is correct
52 Correct 279 ms 66812 KB Output is correct
53 Correct 378 ms 66992 KB Output is correct
54 Correct 380 ms 75080 KB Output is correct
55 Correct 386 ms 71292 KB Output is correct
56 Correct 381 ms 71096 KB Output is correct
57 Correct 317 ms 67284 KB Output is correct
58 Correct 320 ms 66884 KB Output is correct
59 Correct 333 ms 67280 KB Output is correct
60 Correct 360 ms 67280 KB Output is correct
61 Correct 414 ms 67276 KB Output is correct
62 Correct 347 ms 67276 KB Output is correct
63 Correct 371 ms 67184 KB Output is correct
64 Correct 372 ms 67280 KB Output is correct
65 Correct 519 ms 75104 KB Output is correct
66 Correct 521 ms 75104 KB Output is correct
67 Correct 393 ms 71228 KB Output is correct
68 Correct 383 ms 71116 KB Output is correct
69 Correct 389 ms 70760 KB Output is correct
70 Correct 394 ms 70744 KB Output is correct
71 Correct 380 ms 75100 KB Output is correct
72 Correct 388 ms 75100 KB Output is correct
73 Correct 381 ms 72492 KB Output is correct
74 Correct 376 ms 72396 KB Output is correct
75 Correct 317 ms 71900 KB Output is correct
76 Correct 306 ms 75088 KB Output is correct
77 Correct 312 ms 75216 KB Output is correct
78 Correct 387 ms 69176 KB Output is correct
79 Correct 415 ms 68540 KB Output is correct
80 Correct 4429 ms 83560 KB Output is correct
81 Correct 4525 ms 82716 KB Output is correct
82 Correct 4418 ms 79436 KB Output is correct
83 Correct 4472 ms 82732 KB Output is correct
84 Correct 4509 ms 83456 KB Output is correct
85 Correct 4502 ms 79936 KB Output is correct
86 Correct 4457 ms 82860 KB Output is correct
87 Correct 3204 ms 74756 KB Output is correct
88 Correct 4677 ms 74720 KB Output is correct
89 Correct 4594 ms 156916 KB Output is correct
90 Correct 4461 ms 117848 KB Output is correct
91 Correct 4407 ms 117852 KB Output is correct
92 Correct 3547 ms 78748 KB Output is correct
93 Correct 3350 ms 74764 KB Output is correct
94 Correct 4310 ms 78700 KB Output is correct
95 Correct 4469 ms 78696 KB Output is correct
96 Correct 4417 ms 78712 KB Output is correct
97 Correct 4227 ms 78848 KB Output is correct
98 Correct 4361 ms 78668 KB Output is correct
99 Correct 4374 ms 78676 KB Output is correct
100 Execution timed out 6077 ms 157056 KB Time limit exceeded
101 Halted 0 ms 0 KB -