oj.uz

Submission #46422

# Submission time Handle Problem Language Result Execution time Memory
46422 2018-04-20T13:47:32 Z SpaimaCarpatilor Port Facility (JOI17_port_facility) C++17
100 / 100
 3896 ms 656108 KB 
#include<bits/stdc++.h>

using namespace std;

const int NMAX = 1000009;
int N, M, a[NMAX], b[NMAX], p[2 * NMAX], pos[2 * NMAX], ap[NMAX];
const int mod = 1e9 + 7;

int ansMi, ansMa, hansMi, hansMa, mi[5 * NMAX], ma[5 * NMAX], hmi[5 * NMAX], hma[5 * NMAX];

void refresh (int nod, int f1, int f2)
{
    mi[nod] = min (mi[f1], mi[f2]);
    ma[nod] = max (ma[f1], ma[f2]);
    hmi[nod] = (mi[nod] == mi[f1] ? hmi[f1] : hmi[f2]);
    hma[nod] = (ma[nod] == ma[f1] ? hma[f1] : hma[f2]);
}

void build (int nod, int st, int dr)
{
    if (st == dr)
    {
        if (p[st] == 0) mi[nod] = 4 * N, ma[nod] = 0;
        else mi[nod] = ma[nod] = p[st];
        hmi[nod] = hma[nod] = st;
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    build (f1, st, mij);
    build (f2, mij + 1, dr);
    refresh (nod, f1, f2);
}

void query (int nod, int st, int dr, int x, int y)
{
    if (x > y) return ;
    if (x <= st && dr <= y)
    {
        if (mi[nod] < ansMi)
            ansMi = mi[nod], hansMi = hmi[nod];
        if (ma[nod] > ansMa)
            ansMa = ma[nod], hansMa = hma[nod];
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    if (x <= mij) query (f1, st, mij, x, y);
    if (mij < y) query (f2, mij + 1, dr, x, y);
}

void delPos (int nod, int st, int dr, int pos)
{
    if (st == dr)
    {
        mi[nod] = 4 * N, ma[nod] = 0;
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    if (pos <= mij) delPos (f1, st, mij, pos);
    else delPos (f2, mij + 1, dr, pos);
    refresh (nod, f1, f2);
}

void delVal (int x)
{
    delPos (1, 1, 2 * N, a[x]);
    delPos (1, 1, 2 * N, b[x]);
}

void dfs (int nod, int c)
{
    if (ap[nod] != 0 && ap[nod] != c)
    {
        printf ("0\n");
        exit (0);
    }
    if (ap[nod] != 0) return ;
    ap[nod] = c, delVal (nod);
    while (1)
    {
        ansMi = 4 * N, ansMa = 0, query (1, 1, 2 * N, a[nod] + 1, b[nod] - 1);
        if (ansMi > a[nod] && ansMa < b[nod]) break;
        int toDel = 0;
        if (ansMi <= a[nod]) toDel = pos[hansMi];
        else toDel = pos[hansMa];
        dfs (toDel, 3 - c);
    }
}

void check (vector < int > &ids)
{
    for (int i=1; i<=2 * N; i++)
        p[i] = 0;
    for (auto it : ids)
        p[a[it]] = b[it], p[b[it]] = a[it];
    build (1, 1, 2 * N);
    for (auto i : ids)
    {
        ansMi = 4 * N, ansMa = 0, query (1, 1, 2 * N, a[i] + 1, b[i] - 1);
        if (ansMi < a[i] || ansMa > b[i])
        {
            printf ("0\n");
            exit (0);
        }
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N);
for (int i=1; i<=N; i++)
{
    scanf ("%d %d", &a[i], &b[i]);
    p[a[i]] = b[i], p[b[i]] = a[i];
    pos[a[i]] = pos[b[i]] = i;
}
build (1, 1, 2 * N);
int ans = 1;
for (int i=1; i<=N; i++)
    if (ap[i] == 0)
        dfs (i, +1), ans = (ans + ans) % mod;
vector < int > v[2];
for (int i=1; i<=N; i++)
    v[ap[i] - 1].push_back (i);
check (v[0]), check (v[1]);
printf ("%d\n", ans);
return 0;
}

Compilation message

port_facility.cpp: In function 'int main()':
port_facility.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
 ~~~~~~^~~~~~~~~~
port_facility.cpp:115:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &a[i], &b[i]);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 2 ms 532 KB Output is correct
7 Correct 2 ms 536 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 660 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 2 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 2 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 884 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 2 ms 532 KB Output is correct
7 Correct 2 ms 536 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 660 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 2 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 2 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 884 KB Output is correct
25 Correct 4 ms 1084 KB Output is correct
26 Correct 4 ms 1104 KB Output is correct
27 Correct 4 ms 1140 KB Output is correct
28 Correct 4 ms 1140 KB Output is correct
29 Correct 4 ms 1196 KB Output is correct
30 Correct 4 ms 1216 KB Output is correct
31 Correct 5 ms 1252 KB Output is correct
32 Correct 4 ms 1252 KB Output is correct
33 Correct 4 ms 1296 KB Output is correct
34 Correct 4 ms 1328 KB Output is correct
35 Correct 3 ms 1352 KB Output is correct
36 Correct 4 ms 1352 KB Output is correct
37 Correct 5 ms 1392 KB Output is correct
38 Correct 4 ms 1412 KB Output is correct
39 Correct 4 ms 1432 KB Output is correct
40 Correct 5 ms 1452 KB Output is correct
41 Correct 4 ms 1472 KB Output is correct
42 Correct 5 ms 1492 KB Output is correct
43 Correct 3 ms 1512 KB Output is correct
44 Correct 4 ms 1660 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 2 ms 532 KB Output is correct
7 Correct 2 ms 536 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 660 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 2 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 2 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 884 KB Output is correct
25 Correct 4 ms 1084 KB Output is correct
26 Correct 4 ms 1104 KB Output is correct
27 Correct 4 ms 1140 KB Output is correct
28 Correct 4 ms 1140 KB Output is correct
29 Correct 4 ms 1196 KB Output is correct
30 Correct 4 ms 1216 KB Output is correct
31 Correct 5 ms 1252 KB Output is correct
32 Correct 4 ms 1252 KB Output is correct
33 Correct 4 ms 1296 KB Output is correct
34 Correct 4 ms 1328 KB Output is correct
35 Correct 3 ms 1352 KB Output is correct
36 Correct 4 ms 1352 KB Output is correct
37 Correct 5 ms 1392 KB Output is correct
38 Correct 4 ms 1412 KB Output is correct
39 Correct 4 ms 1432 KB Output is correct
40 Correct 5 ms 1452 KB Output is correct
41 Correct 4 ms 1472 KB Output is correct
42 Correct 5 ms 1492 KB Output is correct
43 Correct 3 ms 1512 KB Output is correct
44 Correct 4 ms 1660 KB Output is correct
45 Correct 206 ms 14544 KB Output is correct
46 Correct 203 ms 16280 KB Output is correct
47 Correct 200 ms 16776 KB Output is correct
48 Correct 225 ms 18800 KB Output is correct
49 Correct 206 ms 19360 KB Output is correct
50 Correct 209 ms 21196 KB Output is correct
51 Correct 176 ms 22452 KB Output is correct
52 Correct 132 ms 23032 KB Output is correct
53 Correct 274 ms 24332 KB Output is correct
54 Correct 152 ms 28476 KB Output is correct
55 Correct 148 ms 28476 KB Output is correct
56 Correct 165 ms 29544 KB Output is correct
57 Correct 183 ms 29544 KB Output is correct
58 Correct 158 ms 30632 KB Output is correct
59 Correct 193 ms 31820 KB Output is correct
60 Correct 194 ms 33152 KB Output is correct
61 Correct 202 ms 34300 KB Output is correct
62 Correct 140 ms 35832 KB Output is correct
63 Correct 159 ms 37108 KB Output is correct
64 Correct 174 ms 38112 KB Output is correct
65 Correct 239 ms 42596 KB Output is correct
66 Correct 245 ms 43680 KB Output is correct
67 Correct 217 ms 43680 KB Output is correct
68 Correct 230 ms 44732 KB Output is correct
69 Correct 223 ms 46124 KB Output is correct
70 Correct 233 ms 47332 KB Output is correct
71 Correct 205 ms 50068 KB Output is correct
72 Correct 219 ms 51376 KB Output is correct
73 Correct 201 ms 51744 KB Output is correct
74 Correct 203 ms 52920 KB Output is correct
75 Correct 154 ms 53832 KB Output is correct
76 Correct 173 ms 56484 KB Output is correct
77 Correct 121 ms 57584 KB Output is correct
78 Correct 203 ms 57584 KB Output is correct
79 Correct 206 ms 57584 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 2 ms 532 KB Output is correct
7 Correct 2 ms 536 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 660 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 2 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 2 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 884 KB Output is correct
25 Correct 4 ms 1084 KB Output is correct
26 Correct 4 ms 1104 KB Output is correct
27 Correct 4 ms 1140 KB Output is correct
28 Correct 4 ms 1140 KB Output is correct
29 Correct 4 ms 1196 KB Output is correct
30 Correct 4 ms 1216 KB Output is correct
31 Correct 5 ms 1252 KB Output is correct
32 Correct 4 ms 1252 KB Output is correct
33 Correct 4 ms 1296 KB Output is correct
34 Correct 4 ms 1328 KB Output is correct
35 Correct 3 ms 1352 KB Output is correct
36 Correct 4 ms 1352 KB Output is correct
37 Correct 5 ms 1392 KB Output is correct
38 Correct 4 ms 1412 KB Output is correct
39 Correct 4 ms 1432 KB Output is correct
40 Correct 5 ms 1452 KB Output is correct
41 Correct 4 ms 1472 KB Output is correct
42 Correct 5 ms 1492 KB Output is correct
43 Correct 3 ms 1512 KB Output is correct
44 Correct 4 ms 1660 KB Output is correct
45 Correct 206 ms 14544 KB Output is correct
46 Correct 203 ms 16280 KB Output is correct
47 Correct 200 ms 16776 KB Output is correct
48 Correct 225 ms 18800 KB Output is correct
49 Correct 206 ms 19360 KB Output is correct
50 Correct 209 ms 21196 KB Output is correct
51 Correct 176 ms 22452 KB Output is correct
52 Correct 132 ms 23032 KB Output is correct
53 Correct 274 ms 24332 KB Output is correct
54 Correct 152 ms 28476 KB Output is correct
55 Correct 148 ms 28476 KB Output is correct
56 Correct 165 ms 29544 KB Output is correct
57 Correct 183 ms 29544 KB Output is correct
58 Correct 158 ms 30632 KB Output is correct
59 Correct 193 ms 31820 KB Output is correct
60 Correct 194 ms 33152 KB Output is correct
61 Correct 202 ms 34300 KB Output is correct
62 Correct 140 ms 35832 KB Output is correct
63 Correct 159 ms 37108 KB Output is correct
64 Correct 174 ms 38112 KB Output is correct
65 Correct 239 ms 42596 KB Output is correct
66 Correct 245 ms 43680 KB Output is correct
67 Correct 217 ms 43680 KB Output is correct
68 Correct 230 ms 44732 KB Output is correct
69 Correct 223 ms 46124 KB Output is correct
70 Correct 233 ms 47332 KB Output is correct
71 Correct 205 ms 50068 KB Output is correct
72 Correct 219 ms 51376 KB Output is correct
73 Correct 201 ms 51744 KB Output is correct
74 Correct 203 ms 52920 KB Output is correct
75 Correct 154 ms 53832 KB Output is correct
76 Correct 173 ms 56484 KB Output is correct
77 Correct 121 ms 57584 KB Output is correct
78 Correct 203 ms 57584 KB Output is correct
79 Correct 206 ms 57584 KB Output is correct
80 Correct 2903 ms 160852 KB Output is correct
81 Correct 2843 ms 175004 KB Output is correct
82 Correct 2897 ms 188420 KB Output is correct
83 Correct 2916 ms 204328 KB Output is correct
84 Correct 2931 ms 219108 KB Output is correct
85 Correct 2167 ms 232284 KB Output is correct
86 Correct 2656 ms 248216 KB Output is correct
87 Correct 1948 ms 259720 KB Output is correct
88 Correct 3896 ms 274236 KB Output is correct
89 Correct 2134 ms 319836 KB Output is correct
90 Correct 2144 ms 319836 KB Output is correct
91 Correct 2028 ms 333308 KB Output is correct
92 Correct 2400 ms 333308 KB Output is correct
93 Correct 2213 ms 347084 KB Output is correct
94 Correct 2903 ms 362400 KB Output is correct
95 Correct 2778 ms 377244 KB Output is correct
96 Correct 2755 ms 392012 KB Output is correct
97 Correct 2122 ms 406168 KB Output is correct
98 Correct 2049 ms 421136 KB Output is correct
99 Correct 2322 ms 435676 KB Output is correct
100 Correct 3537 ms 480356 KB Output is correct
101 Correct 3601 ms 494736 KB Output is correct
102 Correct 3013 ms 494736 KB Output is correct
103 Correct 2945 ms 508272 KB Output is correct
104 Correct 2968 ms 522352 KB Output is correct
105 Correct 3004 ms 537600 KB Output is correct
106 Correct 3126 ms 567680 KB Output is correct
107 Correct 3224 ms 582268 KB Output is correct
108 Correct 2812 ms 587812 KB Output is correct
109 Correct 2916 ms 602124 KB Output is correct
110 Correct 2161 ms 625332 KB Output is correct
111 Correct 2066 ms 640472 KB Output is correct
112 Correct 1682 ms 655200 KB Output is correct
113 Correct 2859 ms 655200 KB Output is correct
114 Correct 2819 ms 656108 KB Output is correct