oj.uz

Submission #960368

# Submission time Handle Problem Language Result Execution time Memory
960368 2024-04-10T10:29:44 Z boris_mihov Port Facility (JOI17_port_facility) C++17
22 / 100
 6000 ms 171200 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 1e6 + 10;
const int MOD  = 1e9 + 7;
const int INF  = 1e9;

int n;
struct SegmentTree
{
    struct Node
    {
        int sum;
        bool lazy;

        Node()
        {
            sum = lazy = 0;
        }
    
        friend Node operator + (const Node &left, const Node &right)
        {
            Node result;
            result.sum = left.sum + right.sum;
            return result;
        }
    };

    Node tree[8*MAXN];
    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        tree[node].sum = r - l + 1;
        if (l < r)
        {
            tree[2*node].lazy = 1;
            tree[2*node + 1].lazy = 1;
        }

        tree[node].lazy = 0;
    }

    void update(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy = 1;
            push(node, l, r);
            return;
        }

        int mid = l + r >> 1;
        update(l, mid, 2*node, queryL, queryR);
        update(mid + 1, r, 2*node + 1, queryL, queryR);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    int query(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (queryL <= l && r <= queryR)
        {
            return tree[node].sum;
        }

        int res = 0;
        int mid = l + r >> 1;
        if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR);
        return res;
    }

    void update(int l, int r)
    {
        update(1, 2 * n, 1, l, r);
    }

    int query(int l, int r)
    {
        return query(1, 2 * n, 1, l, r);
    }
};

int a[MAXN];
int b[MAXN];
int prefix[2 * MAXN];
std::vector <int> g[MAXN];
std::pair <int,int> toSort[MAXN];
SegmentTree partTree[2];

int vis[MAXN];
bool dfs(int node)
{
    for (const int &u : g[node])
    {
        if (vis[u] == vis[node])
        {
            // assert(false);
            return false;
        }

        if (vis[u] == 0)
        {
            vis[u] = 3 - vis[node];
            if (!dfs(u)) return false;
        }
    }

    return true;
}

void solve()
{
    std::sort(toSort + 1, toSort + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = toSort[i].first;
        b[i] = toSort[i].second;
    }

    // for (int i = n ; i >= 1 ; --i)
    // {
    //     if (partTree[0].query(b[i], b[i]) && partTree[1].query(b[i], b[i]))
    //     {
    //         std::cout << 0 << '\n';
    //         return;
    //     }

    //     int currentPart = 0;
    //     if (partTree[0].query(b[i], b[i]))
    //     {
    //         currentPart = 1;
    //     }

    //     partTree[currentPart].update(a[i], b[i]);
    //     std::cout << "part: " << a[i] << ' ' << b[i] << " = " << currentPart << '\n';
    // }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = i + 1 ; j <= n ; ++j)
        {
            if (a[j] < b[i] && b[i] < b[j])
            {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    int compCnt = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (!vis[i])
        {
            vis[i] = 1;
            if (!dfs(i))
            {
                std::cout << 0 << '\n';
                return;
            }
 
            compCnt++;
        }
    }

    int ans = 1;
    for (int i = 0 ; i < compCnt ; ++i)
    {
        ans <<= 1;
        if (ans >= MOD) ans -= MOD;
    }

    std::cout << ans << '\n';
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> toSort[i].first >> toSort[i].second;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message

port_facility.cpp: In member function 'void SegmentTree::update(int, int, int, int, int)':
port_facility.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = l + r >> 1;
      |                   ~~^~~
port_facility.cpp: In member function 'int SegmentTree::query(int, int, int, int, int)':
port_facility.cpp:83:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 153852 KB Output is correct
2 Correct 45 ms 153940 KB Output is correct
3 Correct 45 ms 154068 KB Output is correct
4 Correct 49 ms 153940 KB Output is correct
5 Correct 45 ms 153936 KB Output is correct
6 Correct 45 ms 154056 KB Output is correct
7 Correct 45 ms 153920 KB Output is correct
8 Correct 50 ms 154328 KB Output is correct
9 Correct 45 ms 153940 KB Output is correct
10 Correct 46 ms 154192 KB Output is correct
11 Correct 49 ms 153936 KB Output is correct
12 Correct 44 ms 153936 KB Output is correct
13 Correct 45 ms 153860 KB Output is correct
14 Correct 45 ms 153872 KB Output is correct
15 Correct 49 ms 153960 KB Output is correct
16 Correct 45 ms 153940 KB Output is correct
17 Correct 46 ms 153936 KB Output is correct
18 Correct 45 ms 153940 KB Output is correct
19 Correct 45 ms 154044 KB Output is correct
20 Correct 47 ms 154164 KB Output is correct
21 Correct 45 ms 153940 KB Output is correct
22 Correct 47 ms 153944 KB Output is correct
23 Correct 46 ms 153944 KB Output is correct
24 Correct 45 ms 153940 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 153852 KB Output is correct
2 Correct 45 ms 153940 KB Output is correct
3 Correct 45 ms 154068 KB Output is correct
4 Correct 49 ms 153940 KB Output is correct
5 Correct 45 ms 153936 KB Output is correct
6 Correct 45 ms 154056 KB Output is correct
7 Correct 45 ms 153920 KB Output is correct
8 Correct 50 ms 154328 KB Output is correct
9 Correct 45 ms 153940 KB Output is correct
10 Correct 46 ms 154192 KB Output is correct
11 Correct 49 ms 153936 KB Output is correct
12 Correct 44 ms 153936 KB Output is correct
13 Correct 45 ms 153860 KB Output is correct
14 Correct 45 ms 153872 KB Output is correct
15 Correct 49 ms 153960 KB Output is correct
16 Correct 45 ms 153940 KB Output is correct
17 Correct 46 ms 153936 KB Output is correct
18 Correct 45 ms 153940 KB Output is correct
19 Correct 45 ms 154044 KB Output is correct
20 Correct 47 ms 154164 KB Output is correct
21 Correct 45 ms 153940 KB Output is correct
22 Correct 47 ms 153944 KB Output is correct
23 Correct 46 ms 153944 KB Output is correct
24 Correct 45 ms 153940 KB Output is correct
25 Correct 51 ms 154192 KB Output is correct
26 Correct 53 ms 154312 KB Output is correct
27 Correct 50 ms 154196 KB Output is correct
28 Correct 51 ms 154448 KB Output is correct
29 Correct 51 ms 154452 KB Output is correct
30 Correct 51 ms 154552 KB Output is correct
31 Correct 51 ms 154448 KB Output is correct
32 Correct 50 ms 154204 KB Output is correct
33 Correct 51 ms 154184 KB Output is correct
34 Correct 55 ms 154196 KB Output is correct
35 Correct 50 ms 153940 KB Output is correct
36 Correct 50 ms 154120 KB Output is correct
37 Correct 64 ms 170064 KB Output is correct
38 Correct 63 ms 162304 KB Output is correct
39 Correct 50 ms 154192 KB Output is correct
40 Correct 50 ms 153940 KB Output is correct
41 Correct 59 ms 162128 KB Output is correct
42 Correct 61 ms 162300 KB Output is correct
43 Correct 51 ms 154060 KB Output is correct
44 Correct 51 ms 154192 KB Output is correct

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 153852 KB Output is correct
2 Correct 45 ms 153940 KB Output is correct
3 Correct 45 ms 154068 KB Output is correct
4 Correct 49 ms 153940 KB Output is correct
5 Correct 45 ms 153936 KB Output is correct
6 Correct 45 ms 154056 KB Output is correct
7 Correct 45 ms 153920 KB Output is correct
8 Correct 50 ms 154328 KB Output is correct
9 Correct 45 ms 153940 KB Output is correct
10 Correct 46 ms 154192 KB Output is correct
11 Correct 49 ms 153936 KB Output is correct
12 Correct 44 ms 153936 KB Output is correct
13 Correct 45 ms 153860 KB Output is correct
14 Correct 45 ms 153872 KB Output is correct
15 Correct 49 ms 153960 KB Output is correct
16 Correct 45 ms 153940 KB Output is correct
17 Correct 46 ms 153936 KB Output is correct
18 Correct 45 ms 153940 KB Output is correct
19 Correct 45 ms 154044 KB Output is correct
20 Correct 47 ms 154164 KB Output is correct
21 Correct 45 ms 153940 KB Output is correct
22 Correct 47 ms 153944 KB Output is correct
23 Correct 46 ms 153944 KB Output is correct
24 Correct 45 ms 153940 KB Output is correct
25 Correct 51 ms 154192 KB Output is correct
26 Correct 53 ms 154312 KB Output is correct
27 Correct 50 ms 154196 KB Output is correct
28 Correct 51 ms 154448 KB Output is correct
29 Correct 51 ms 154452 KB Output is correct
30 Correct 51 ms 154552 KB Output is correct
31 Correct 51 ms 154448 KB Output is correct
32 Correct 50 ms 154204 KB Output is correct
33 Correct 51 ms 154184 KB Output is correct
34 Correct 55 ms 154196 KB Output is correct
35 Correct 50 ms 153940 KB Output is correct
36 Correct 50 ms 154120 KB Output is correct
37 Correct 64 ms 170064 KB Output is correct
38 Correct 63 ms 162304 KB Output is correct
39 Correct 50 ms 154192 KB Output is correct
40 Correct 50 ms 153940 KB Output is correct
41 Correct 59 ms 162128 KB Output is correct
42 Correct 61 ms 162300 KB Output is correct
43 Correct 51 ms 154060 KB Output is correct
44 Correct 51 ms 154192 KB Output is correct
45 Execution timed out 6096 ms 171200 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 153852 KB Output is correct
2 Correct 45 ms 153940 KB Output is correct
3 Correct 45 ms 154068 KB Output is correct
4 Correct 49 ms 153940 KB Output is correct
5 Correct 45 ms 153936 KB Output is correct
6 Correct 45 ms 154056 KB Output is correct
7 Correct 45 ms 153920 KB Output is correct
8 Correct 50 ms 154328 KB Output is correct
9 Correct 45 ms 153940 KB Output is correct
10 Correct 46 ms 154192 KB Output is correct
11 Correct 49 ms 153936 KB Output is correct
12 Correct 44 ms 153936 KB Output is correct
13 Correct 45 ms 153860 KB Output is correct
14 Correct 45 ms 153872 KB Output is correct
15 Correct 49 ms 153960 KB Output is correct
16 Correct 45 ms 153940 KB Output is correct
17 Correct 46 ms 153936 KB Output is correct
18 Correct 45 ms 153940 KB Output is correct
19 Correct 45 ms 154044 KB Output is correct
20 Correct 47 ms 154164 KB Output is correct
21 Correct 45 ms 153940 KB Output is correct
22 Correct 47 ms 153944 KB Output is correct
23 Correct 46 ms 153944 KB Output is correct
24 Correct 45 ms 153940 KB Output is correct
25 Correct 51 ms 154192 KB Output is correct
26 Correct 53 ms 154312 KB Output is correct
27 Correct 50 ms 154196 KB Output is correct
28 Correct 51 ms 154448 KB Output is correct
29 Correct 51 ms 154452 KB Output is correct
30 Correct 51 ms 154552 KB Output is correct
31 Correct 51 ms 154448 KB Output is correct
32 Correct 50 ms 154204 KB Output is correct
33 Correct 51 ms 154184 KB Output is correct
34 Correct 55 ms 154196 KB Output is correct
35 Correct 50 ms 153940 KB Output is correct
36 Correct 50 ms 154120 KB Output is correct
37 Correct 64 ms 170064 KB Output is correct
38 Correct 63 ms 162304 KB Output is correct
39 Correct 50 ms 154192 KB Output is correct
40 Correct 50 ms 153940 KB Output is correct
41 Correct 59 ms 162128 KB Output is correct
42 Correct 61 ms 162300 KB Output is correct
43 Correct 51 ms 154060 KB Output is correct
44 Correct 51 ms 154192 KB Output is correct
45 Execution timed out 6096 ms 171200 KB Time limit exceeded
46 Halted 0 ms 0 KB -