oj.uz

Submission #800186

# Submission time Handle Problem Language Result Execution time Memory
800186 2023-08-01T11:25:00 Z vjudge1 Port Facility (JOI17_port_facility) C++14
78 / 100
 6000 ms 248928 KB 
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const ll N = (1 << 21), mod = 1e9 + 7 ;
bool flag, us[N + 1] ;
ll n, cnt, color[N + 1], a[N + 1], b[N + 1] ;
pair<ll, ll> mn[2 * N + 1], mx[2 * N + 1] ;
ll 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(ll 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

# Verdict Execution time Memory Grader output
1 Correct 97 ms 131620 KB Output is correct
2 Correct 97 ms 131532 KB Output is correct
3 Correct 97 ms 131656 KB Output is correct
4 Correct 97 ms 131536 KB Output is correct
5 Correct 100 ms 131660 KB Output is correct
6 Correct 97 ms 131548 KB Output is correct
7 Correct 97 ms 131560 KB Output is correct
8 Correct 98 ms 131660 KB Output is correct
9 Correct 98 ms 131656 KB Output is correct
10 Correct 99 ms 131660 KB Output is correct
11 Correct 100 ms 131652 KB Output is correct
12 Correct 98 ms 131656 KB Output is correct
13 Correct 99 ms 131552 KB Output is correct
14 Correct 98 ms 131604 KB Output is correct
15 Correct 100 ms 131632 KB Output is correct
16 Correct 104 ms 131616 KB Output is correct
17 Correct 99 ms 131656 KB Output is correct
18 Correct 99 ms 131632 KB Output is correct
19 Correct 103 ms 131580 KB Output is correct
20 Correct 99 ms 131652 KB Output is correct
21 Correct 99 ms 131532 KB Output is correct
22 Correct 98 ms 131548 KB Output is correct
23 Correct 98 ms 131532 KB Output is correct
24 Correct 104 ms 131576 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 131620 KB Output is correct
2 Correct 97 ms 131532 KB Output is correct
3 Correct 97 ms 131656 KB Output is correct
4 Correct 97 ms 131536 KB Output is correct
5 Correct 100 ms 131660 KB Output is correct
6 Correct 97 ms 131548 KB Output is correct
7 Correct 97 ms 131560 KB Output is correct
8 Correct 98 ms 131660 KB Output is correct
9 Correct 98 ms 131656 KB Output is correct
10 Correct 99 ms 131660 KB Output is correct
11 Correct 100 ms 131652 KB Output is correct
12 Correct 98 ms 131656 KB Output is correct
13 Correct 99 ms 131552 KB Output is correct
14 Correct 98 ms 131604 KB Output is correct
15 Correct 100 ms 131632 KB Output is correct
16 Correct 104 ms 131616 KB Output is correct
17 Correct 99 ms 131656 KB Output is correct
18 Correct 99 ms 131632 KB Output is correct
19 Correct 103 ms 131580 KB Output is correct
20 Correct 99 ms 131652 KB Output is correct
21 Correct 99 ms 131532 KB Output is correct
22 Correct 98 ms 131548 KB Output is correct
23 Correct 98 ms 131532 KB Output is correct
24 Correct 104 ms 131576 KB Output is correct
25 Correct 115 ms 131800 KB Output is correct
26 Correct 105 ms 131784 KB Output is correct
27 Correct 105 ms 131716 KB Output is correct
28 Correct 105 ms 131692 KB Output is correct
29 Correct 106 ms 131784 KB Output is correct
30 Correct 114 ms 131792 KB Output is correct
31 Correct 104 ms 131772 KB Output is correct
32 Correct 105 ms 131700 KB Output is correct
33 Correct 104 ms 131680 KB Output is correct
34 Correct 108 ms 131784 KB Output is correct
35 Correct 108 ms 131728 KB Output is correct
36 Correct 103 ms 131688 KB Output is correct
37 Correct 102 ms 131832 KB Output is correct
38 Correct 107 ms 131780 KB Output is correct
39 Correct 103 ms 131704 KB Output is correct
40 Correct 103 ms 131680 KB Output is correct
41 Correct 106 ms 131864 KB Output is correct
42 Correct 105 ms 131812 KB Output is correct
43 Correct 109 ms 131860 KB Output is correct
44 Correct 104 ms 131856 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 131620 KB Output is correct
2 Correct 97 ms 131532 KB Output is correct
3 Correct 97 ms 131656 KB Output is correct
4 Correct 97 ms 131536 KB Output is correct
5 Correct 100 ms 131660 KB Output is correct
6 Correct 97 ms 131548 KB Output is correct
7 Correct 97 ms 131560 KB Output is correct
8 Correct 98 ms 131660 KB Output is correct
9 Correct 98 ms 131656 KB Output is correct
10 Correct 99 ms 131660 KB Output is correct
11 Correct 100 ms 131652 KB Output is correct
12 Correct 98 ms 131656 KB Output is correct
13 Correct 99 ms 131552 KB Output is correct
14 Correct 98 ms 131604 KB Output is correct
15 Correct 100 ms 131632 KB Output is correct
16 Correct 104 ms 131616 KB Output is correct
17 Correct 99 ms 131656 KB Output is correct
18 Correct 99 ms 131632 KB Output is correct
19 Correct 103 ms 131580 KB Output is correct
20 Correct 99 ms 131652 KB Output is correct
21 Correct 99 ms 131532 KB Output is correct
22 Correct 98 ms 131548 KB Output is correct
23 Correct 98 ms 131532 KB Output is correct
24 Correct 104 ms 131576 KB Output is correct
25 Correct 115 ms 131800 KB Output is correct
26 Correct 105 ms 131784 KB Output is correct
27 Correct 105 ms 131716 KB Output is correct
28 Correct 105 ms 131692 KB Output is correct
29 Correct 106 ms 131784 KB Output is correct
30 Correct 114 ms 131792 KB Output is correct
31 Correct 104 ms 131772 KB Output is correct
32 Correct 105 ms 131700 KB Output is correct
33 Correct 104 ms 131680 KB Output is correct
34 Correct 108 ms 131784 KB Output is correct
35 Correct 108 ms 131728 KB Output is correct
36 Correct 103 ms 131688 KB Output is correct
37 Correct 102 ms 131832 KB Output is correct
38 Correct 107 ms 131780 KB Output is correct
39 Correct 103 ms 131704 KB Output is correct
40 Correct 103 ms 131680 KB Output is correct
41 Correct 106 ms 131864 KB Output is correct
42 Correct 105 ms 131812 KB Output is correct
43 Correct 109 ms 131860 KB Output is correct
44 Correct 104 ms 131856 KB Output is correct
45 Correct 442 ms 135192 KB Output is correct
46 Correct 449 ms 136196 KB Output is correct
47 Correct 442 ms 134444 KB Output is correct
48 Correct 464 ms 136136 KB Output is correct
49 Correct 441 ms 134632 KB Output is correct
50 Correct 461 ms 135964 KB Output is correct
51 Correct 457 ms 135908 KB Output is correct
52 Correct 341 ms 133284 KB Output is correct
53 Correct 423 ms 133352 KB Output is correct
54 Correct 453 ms 141824 KB Output is correct
55 Correct 443 ms 138040 KB Output is correct
56 Correct 431 ms 137940 KB Output is correct
57 Correct 369 ms 134112 KB Output is correct
58 Correct 341 ms 133260 KB Output is correct
59 Correct 418 ms 134212 KB Output is correct
60 Correct 428 ms 134092 KB Output is correct
61 Correct 431 ms 134036 KB Output is correct
62 Correct 398 ms 134072 KB Output is correct
63 Correct 428 ms 134100 KB Output is correct
64 Correct 443 ms 134204 KB Output is correct
65 Correct 694 ms 141920 KB Output is correct
66 Correct 592 ms 141860 KB Output is correct
67 Correct 456 ms 138012 KB Output is correct
68 Correct 444 ms 137932 KB Output is correct
69 Correct 461 ms 137520 KB Output is correct
70 Correct 456 ms 137576 KB Output is correct
71 Correct 442 ms 141932 KB Output is correct
72 Correct 455 ms 141848 KB Output is correct
73 Correct 427 ms 139320 KB Output is correct
74 Correct 431 ms 139340 KB Output is correct
75 Correct 384 ms 138768 KB Output is correct
76 Correct 382 ms 141912 KB Output is correct
77 Correct 359 ms 141932 KB Output is correct
78 Correct 438 ms 135944 KB Output is correct
79 Correct 442 ms 135296 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 131620 KB Output is correct
2 Correct 97 ms 131532 KB Output is correct
3 Correct 97 ms 131656 KB Output is correct
4 Correct 97 ms 131536 KB Output is correct
5 Correct 100 ms 131660 KB Output is correct
6 Correct 97 ms 131548 KB Output is correct
7 Correct 97 ms 131560 KB Output is correct
8 Correct 98 ms 131660 KB Output is correct
9 Correct 98 ms 131656 KB Output is correct
10 Correct 99 ms 131660 KB Output is correct
11 Correct 100 ms 131652 KB Output is correct
12 Correct 98 ms 131656 KB Output is correct
13 Correct 99 ms 131552 KB Output is correct
14 Correct 98 ms 131604 KB Output is correct
15 Correct 100 ms 131632 KB Output is correct
16 Correct 104 ms 131616 KB Output is correct
17 Correct 99 ms 131656 KB Output is correct
18 Correct 99 ms 131632 KB Output is correct
19 Correct 103 ms 131580 KB Output is correct
20 Correct 99 ms 131652 KB Output is correct
21 Correct 99 ms 131532 KB Output is correct
22 Correct 98 ms 131548 KB Output is correct
23 Correct 98 ms 131532 KB Output is correct
24 Correct 104 ms 131576 KB Output is correct
25 Correct 115 ms 131800 KB Output is correct
26 Correct 105 ms 131784 KB Output is correct
27 Correct 105 ms 131716 KB Output is correct
28 Correct 105 ms 131692 KB Output is correct
29 Correct 106 ms 131784 KB Output is correct
30 Correct 114 ms 131792 KB Output is correct
31 Correct 104 ms 131772 KB Output is correct
32 Correct 105 ms 131700 KB Output is correct
33 Correct 104 ms 131680 KB Output is correct
34 Correct 108 ms 131784 KB Output is correct
35 Correct 108 ms 131728 KB Output is correct
36 Correct 103 ms 131688 KB Output is correct
37 Correct 102 ms 131832 KB Output is correct
38 Correct 107 ms 131780 KB Output is correct
39 Correct 103 ms 131704 KB Output is correct
40 Correct 103 ms 131680 KB Output is correct
41 Correct 106 ms 131864 KB Output is correct
42 Correct 105 ms 131812 KB Output is correct
43 Correct 109 ms 131860 KB Output is correct
44 Correct 104 ms 131856 KB Output is correct
45 Correct 442 ms 135192 KB Output is correct
46 Correct 449 ms 136196 KB Output is correct
47 Correct 442 ms 134444 KB Output is correct
48 Correct 464 ms 136136 KB Output is correct
49 Correct 441 ms 134632 KB Output is correct
50 Correct 461 ms 135964 KB Output is correct
51 Correct 457 ms 135908 KB Output is correct
52 Correct 341 ms 133284 KB Output is correct
53 Correct 423 ms 133352 KB Output is correct
54 Correct 453 ms 141824 KB Output is correct
55 Correct 443 ms 138040 KB Output is correct
56 Correct 431 ms 137940 KB Output is correct
57 Correct 369 ms 134112 KB Output is correct
58 Correct 341 ms 133260 KB Output is correct
59 Correct 418 ms 134212 KB Output is correct
60 Correct 428 ms 134092 KB Output is correct
61 Correct 431 ms 134036 KB Output is correct
62 Correct 398 ms 134072 KB Output is correct
63 Correct 428 ms 134100 KB Output is correct
64 Correct 443 ms 134204 KB Output is correct
65 Correct 694 ms 141920 KB Output is correct
66 Correct 592 ms 141860 KB Output is correct
67 Correct 456 ms 138012 KB Output is correct
68 Correct 444 ms 137932 KB Output is correct
69 Correct 461 ms 137520 KB Output is correct
70 Correct 456 ms 137576 KB Output is correct
71 Correct 442 ms 141932 KB Output is correct
72 Correct 455 ms 141848 KB Output is correct
73 Correct 427 ms 139320 KB Output is correct
74 Correct 431 ms 139340 KB Output is correct
75 Correct 384 ms 138768 KB Output is correct
76 Correct 382 ms 141912 KB Output is correct
77 Correct 359 ms 141932 KB Output is correct
78 Correct 438 ms 135944 KB Output is correct
79 Correct 442 ms 135296 KB Output is correct
80 Correct 4874 ms 161012 KB Output is correct
81 Correct 4855 ms 174540 KB Output is correct
82 Correct 4821 ms 171516 KB Output is correct
83 Correct 4840 ms 174616 KB Output is correct
84 Correct 4881 ms 175508 KB Output is correct
85 Correct 4816 ms 171908 KB Output is correct
86 Correct 4785 ms 174612 KB Output is correct
87 Correct 3516 ms 162836 KB Output is correct
88 Correct 5088 ms 162852 KB Output is correct
89 Correct 5065 ms 248868 KB Output is correct
90 Correct 4984 ms 209804 KB Output is correct
91 Correct 5188 ms 209696 KB Output is correct
92 Correct 3696 ms 170652 KB Output is correct
93 Correct 3682 ms 162816 KB Output is correct
94 Correct 4569 ms 170612 KB Output is correct
95 Correct 4693 ms 170664 KB Output is correct
96 Correct 4782 ms 170748 KB Output is correct
97 Correct 4516 ms 170720 KB Output is correct
98 Correct 4747 ms 170664 KB Output is correct
99 Correct 4706 ms 170616 KB Output is correct
100 Execution timed out 6064 ms 248928 KB Time limit exceeded
101 Halted 0 ms 0 KB -