oj.uz

Submission #96478

# Submission time Handle Problem Language Result Execution time Memory
96478 2019-02-09T15:28:23 Z updown1 Port Facility (JOI17_port_facility) C++17
100 / 100
 5397 ms 1017440 KB 
/*
https://translate.google.com/translate?sl=auto&tl=en&u=https%3A%2F%2Fwww.ioi-jp.org%2Fcamp%2F2017%2F2017-sp-tasks%2F2017-sp-d1-port_facility-review.pdf
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, P)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//500,000,000 operations
const int MAXN = 2000001, MOD = 1000000007;
//Global Variables
int N, inp[MAXN][2], out = 1, color[MAXN], indst[4*MAXN+1], indend[4*MAXN+1];
pair<int, int> onend[MAXN], onst[MAXN];
vector<pair<int, int> > treest[4*MAXN+1], treeend[4*MAXN+1];
bool del[MAXN];
queue<int> next1;

void build (int ind, int L, int R) {
    if (L == R) {
        if (onst[L].a  != MOD) treest[ind].pb(onst[L]);
        if (onend[L].a != MOD) treeend[ind].pb(onend[L]);
        indst[ind] = treest[ind].size()-1;
        indend[ind] = treeend[ind].size()-1;
        return;
    }
    build(ind*2, L, (L+R)/2); build(ind*2+1, (L+R)/2+1, R);
    int a = 0, b = 0;
    For (i, 0, treest[ind*2].size() + treest[ind*2+1].size()) {
        int x = MOD, y = MOD;
        if (treest[ind*2].size() != a) x = treest[ind*2][a].a;
        if (treest[ind*2+1].size() != b) y = treest[ind*2+1][b].a;
        if (x < y) {
            treest[ind].pb(treest[ind*2][a]);
            a++;
        }
        else {
            treest[ind].pb(treest[ind*2+1][b]);
            b++;
        }
    }
    a = 0, b = 0;
    For (i, 0, treeend[ind*2].size() + treeend[ind*2+1].size()) {
        int x = -1, y = -1;
        if (treeend[ind*2].size() != a) x = treeend[ind*2][a].a;
        if (treeend[ind*2+1].size() != b) y = treeend[ind*2+1][b].a;
        if (x > y) {
            treeend[ind].pb(treeend[ind*2][a]);
            a++;
        }
        else {
            treeend[ind].pb(treeend[ind*2+1][b]);
            b++;
        }
    }
    indst[ind] = treest[ind].size()-1; indend[ind] = treeend[ind].size()-1;
}
void queryst(int ind, int L, int R, int oL, int oR, int v, int x) {
    if (oR < L || R < oL) return;
    if (oL <= L && R <= oR) {
        while (indst[ind] != -1 && treest[ind][indst[ind]].a > v) {
            int i = treest[ind][indst[ind]].b;
            if (!del[i]) {
                del[i] = true;
                color[i] = x;
                //w<< "set" s i s x<<e;
                next1.push(i);
            }
            else if (color[i] != x) {
                //w<< "bad" s i c x s color[i]<<e;
                w<< 0<<e;
                exit(0);
            }
            indst[ind] --;
        }
        return;
    }
    queryst(ind*2, L, (L+R)/2, oL, oR, v, x); queryst(ind*2+1, (L+R)/2+1, R, oL, oR, v, x);
}
void queryend(int ind, int L, int R, int oL, int oR, int v, int x) {
    if (oR < L || R < oL) return;
    if (oL <= L && R <= oR) {
        while (indend[ind] != -1 && treeend[ind][indend[ind]].a < v) {
            int i = treeend[ind][indend[ind]].b;
            if (!del[i]) {
                del[i] = true;
                color[i] = x;
                //w<< "set" s i s x<<e;
                next1.push(i);
            }
            else if (color[i] != x) {
                //w<< "bad" s i c x s color[i]<<e;
                w<< 0<<e;
                exit(0);
            }
            indend[ind] --;
        }
        return;
    }
    queryend(ind*2, L, (L+R)/2, oL, oR, v, x); queryend(ind*2+1, (L+R)/2+1, R, oL, oR, v, x);
}

main() {
    //ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    //For (i, 0, MAXN) tree[i] = mp(MOD, MOD);
    ffi {
        cin >> inp[i][0] >> inp[i][1];
        onst[inp[i][0]] = mp(inp[i][1], i);  /// tree[st] = end
        onst[inp[i][1]] = mp(MOD, -1);
        onend[inp[i][1]] = mp(inp[i][0], i); /// tree[end] = st
        onend[inp[i][0]] = mp(MOD, -1);
        color[i] = 2;
    }
    build(1, 1, 2*N);
    ffi if (!del[i]) {
        /// bfs
        //w<< "set" s i s 1<<e;
        color[i] = 1;
        out *= 2;
        out %= MOD;
        del[i] = true;
        next1.push(i);
        //w<< "going at" s i+1<<e;
        while (!next1.empty()) {
            int a = next1.front(); next1.pop();
            //w<< "at" s a+1<<e;
            /// guaranteed not deleted, but del[a] = false
            queryst(1, 1, 2*N, inp[a][0], inp[a][1], inp[a][1], 1-color[a]);
            queryend(1, 1, 2*N, inp[a][0], inp[a][1], inp[a][0], 1-color[a]);
        }
    }
    w<< out<<e;
}

Compilation message

port_facility.cpp: In function 'void build(int, int, int)':
port_facility.cpp:7:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define For(i, a, b) for(int i=a; i<b; i++)
port_facility.cpp:39:10:
     For (i, 0, treest[ind*2].size() + treest[ind*2+1].size()) {
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:39:5: note: in expansion of macro 'For'
     For (i, 0, treest[ind*2].size() + treest[ind*2+1].size()) {
     ^~~
port_facility.cpp:41:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (treest[ind*2].size() != a) x = treest[ind*2][a].a;
                                  ^
port_facility.cpp:42:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (treest[ind*2+1].size() != b) y = treest[ind*2+1][b].a;
                                    ^
port_facility.cpp:7:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define For(i, a, b) for(int i=a; i<b; i++)
port_facility.cpp:53:10:
     For (i, 0, treeend[ind*2].size() + treeend[ind*2+1].size()) {
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:53:5: note: in expansion of macro 'For'
     For (i, 0, treeend[ind*2].size() + treeend[ind*2+1].size()) {
     ^~~
port_facility.cpp:55:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (treeend[ind*2].size() != a) x = treeend[ind*2][a].a;
                                   ^
port_facility.cpp:56:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (treeend[ind*2+1].size() != b) y = treeend[ind*2+1][b].a;
                                     ^
port_facility.cpp: At global scope:
port_facility.cpp:113:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 376160 KB Output is correct
2 Correct 321 ms 376220 KB Output is correct
3 Correct 311 ms 376164 KB Output is correct
4 Correct 312 ms 376160 KB Output is correct
5 Correct 296 ms 376056 KB Output is correct
6 Correct 309 ms 376148 KB Output is correct
7 Correct 316 ms 376144 KB Output is correct
8 Correct 334 ms 376184 KB Output is correct
9 Correct 347 ms 376180 KB Output is correct
10 Correct 332 ms 376184 KB Output is correct
11 Correct 315 ms 376228 KB Output is correct
12 Correct 304 ms 376056 KB Output is correct
13 Correct 342 ms 376120 KB Output is correct
14 Correct 297 ms 376056 KB Output is correct
15 Correct 322 ms 376184 KB Output is correct
16 Correct 315 ms 376124 KB Output is correct
17 Correct 319 ms 376184 KB Output is correct
18 Correct 334 ms 376184 KB Output is correct
19 Correct 334 ms 376056 KB Output is correct
20 Correct 321 ms 376120 KB Output is correct
21 Correct 292 ms 376096 KB Output is correct
22 Correct 299 ms 376184 KB Output is correct
23 Correct 312 ms 376112 KB Output is correct
24 Correct 329 ms 376184 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 376160 KB Output is correct
2 Correct 321 ms 376220 KB Output is correct
3 Correct 311 ms 376164 KB Output is correct
4 Correct 312 ms 376160 KB Output is correct
5 Correct 296 ms 376056 KB Output is correct
6 Correct 309 ms 376148 KB Output is correct
7 Correct 316 ms 376144 KB Output is correct
8 Correct 334 ms 376184 KB Output is correct
9 Correct 347 ms 376180 KB Output is correct
10 Correct 332 ms 376184 KB Output is correct
11 Correct 315 ms 376228 KB Output is correct
12 Correct 304 ms 376056 KB Output is correct
13 Correct 342 ms 376120 KB Output is correct
14 Correct 297 ms 376056 KB Output is correct
15 Correct 322 ms 376184 KB Output is correct
16 Correct 315 ms 376124 KB Output is correct
17 Correct 319 ms 376184 KB Output is correct
18 Correct 334 ms 376184 KB Output is correct
19 Correct 334 ms 376056 KB Output is correct
20 Correct 321 ms 376120 KB Output is correct
21 Correct 292 ms 376096 KB Output is correct
22 Correct 299 ms 376184 KB Output is correct
23 Correct 312 ms 376112 KB Output is correct
24 Correct 329 ms 376184 KB Output is correct
25 Correct 295 ms 377180 KB Output is correct
26 Correct 303 ms 377016 KB Output is correct
27 Correct 302 ms 377188 KB Output is correct
28 Correct 300 ms 377180 KB Output is correct
29 Correct 298 ms 376960 KB Output is correct
30 Correct 300 ms 377080 KB Output is correct
31 Correct 299 ms 376952 KB Output is correct
32 Correct 299 ms 377028 KB Output is correct
33 Correct 296 ms 377048 KB Output is correct
34 Correct 291 ms 377108 KB Output is correct
35 Correct 307 ms 377196 KB Output is correct
36 Correct 295 ms 376824 KB Output is correct
37 Correct 290 ms 376824 KB Output is correct
38 Correct 338 ms 377052 KB Output is correct
39 Correct 328 ms 377084 KB Output is correct
40 Correct 335 ms 377132 KB Output is correct
41 Correct 295 ms 376904 KB Output is correct
42 Correct 315 ms 376948 KB Output is correct
43 Correct 297 ms 376952 KB Output is correct
44 Correct 344 ms 377000 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 376160 KB Output is correct
2 Correct 321 ms 376220 KB Output is correct
3 Correct 311 ms 376164 KB Output is correct
4 Correct 312 ms 376160 KB Output is correct
5 Correct 296 ms 376056 KB Output is correct
6 Correct 309 ms 376148 KB Output is correct
7 Correct 316 ms 376144 KB Output is correct
8 Correct 334 ms 376184 KB Output is correct
9 Correct 347 ms 376180 KB Output is correct
10 Correct 332 ms 376184 KB Output is correct
11 Correct 315 ms 376228 KB Output is correct
12 Correct 304 ms 376056 KB Output is correct
13 Correct 342 ms 376120 KB Output is correct
14 Correct 297 ms 376056 KB Output is correct
15 Correct 322 ms 376184 KB Output is correct
16 Correct 315 ms 376124 KB Output is correct
17 Correct 319 ms 376184 KB Output is correct
18 Correct 334 ms 376184 KB Output is correct
19 Correct 334 ms 376056 KB Output is correct
20 Correct 321 ms 376120 KB Output is correct
21 Correct 292 ms 376096 KB Output is correct
22 Correct 299 ms 376184 KB Output is correct
23 Correct 312 ms 376112 KB Output is correct
24 Correct 329 ms 376184 KB Output is correct
25 Correct 295 ms 377180 KB Output is correct
26 Correct 303 ms 377016 KB Output is correct
27 Correct 302 ms 377188 KB Output is correct
28 Correct 300 ms 377180 KB Output is correct
29 Correct 298 ms 376960 KB Output is correct
30 Correct 300 ms 377080 KB Output is correct
31 Correct 299 ms 376952 KB Output is correct
32 Correct 299 ms 377028 KB Output is correct
33 Correct 296 ms 377048 KB Output is correct
34 Correct 291 ms 377108 KB Output is correct
35 Correct 307 ms 377196 KB Output is correct
36 Correct 295 ms 376824 KB Output is correct
37 Correct 290 ms 376824 KB Output is correct
38 Correct 338 ms 377052 KB Output is correct
39 Correct 328 ms 377084 KB Output is correct
40 Correct 335 ms 377132 KB Output is correct
41 Correct 295 ms 376904 KB Output is correct
42 Correct 315 ms 376948 KB Output is correct
43 Correct 297 ms 376952 KB Output is correct
44 Correct 344 ms 377000 KB Output is correct
45 Correct 709 ms 433312 KB Output is correct
46 Correct 696 ms 433200 KB Output is correct
47 Correct 647 ms 433260 KB Output is correct
48 Correct 687 ms 433360 KB Output is correct
49 Correct 729 ms 433176 KB Output is correct
50 Correct 582 ms 433320 KB Output is correct
51 Correct 561 ms 433060 KB Output is correct
52 Correct 630 ms 433580 KB Output is correct
53 Correct 691 ms 428908 KB Output is correct
54 Correct 445 ms 428872 KB Output is correct
55 Correct 457 ms 429012 KB Output is correct
56 Correct 447 ms 428956 KB Output is correct
57 Correct 615 ms 432384 KB Output is correct
58 Correct 700 ms 432272 KB Output is correct
59 Correct 744 ms 436004 KB Output is correct
60 Correct 763 ms 434924 KB Output is correct
61 Correct 713 ms 434100 KB Output is correct
62 Correct 571 ms 435744 KB Output is correct
63 Correct 563 ms 434668 KB Output is correct
64 Correct 655 ms 434084 KB Output is correct
65 Correct 507 ms 430700 KB Output is correct
66 Correct 543 ms 430672 KB Output is correct
67 Correct 674 ms 430644 KB Output is correct
68 Correct 700 ms 430668 KB Output is correct
69 Correct 636 ms 432544 KB Output is correct
70 Correct 709 ms 432620 KB Output is correct
71 Correct 568 ms 428912 KB Output is correct
72 Correct 600 ms 429052 KB Output is correct
73 Correct 685 ms 429060 KB Output is correct
74 Correct 644 ms 428880 KB Output is correct
75 Correct 675 ms 433484 KB Output is correct
76 Correct 697 ms 433520 KB Output is correct
77 Correct 629 ms 433608 KB Output is correct
78 Correct 747 ms 433300 KB Output is correct
79 Correct 653 ms 433132 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 376160 KB Output is correct
2 Correct 321 ms 376220 KB Output is correct
3 Correct 311 ms 376164 KB Output is correct
4 Correct 312 ms 376160 KB Output is correct
5 Correct 296 ms 376056 KB Output is correct
6 Correct 309 ms 376148 KB Output is correct
7 Correct 316 ms 376144 KB Output is correct
8 Correct 334 ms 376184 KB Output is correct
9 Correct 347 ms 376180 KB Output is correct
10 Correct 332 ms 376184 KB Output is correct
11 Correct 315 ms 376228 KB Output is correct
12 Correct 304 ms 376056 KB Output is correct
13 Correct 342 ms 376120 KB Output is correct
14 Correct 297 ms 376056 KB Output is correct
15 Correct 322 ms 376184 KB Output is correct
16 Correct 315 ms 376124 KB Output is correct
17 Correct 319 ms 376184 KB Output is correct
18 Correct 334 ms 376184 KB Output is correct
19 Correct 334 ms 376056 KB Output is correct
20 Correct 321 ms 376120 KB Output is correct
21 Correct 292 ms 376096 KB Output is correct
22 Correct 299 ms 376184 KB Output is correct
23 Correct 312 ms 376112 KB Output is correct
24 Correct 329 ms 376184 KB Output is correct
25 Correct 295 ms 377180 KB Output is correct
26 Correct 303 ms 377016 KB Output is correct
27 Correct 302 ms 377188 KB Output is correct
28 Correct 300 ms 377180 KB Output is correct
29 Correct 298 ms 376960 KB Output is correct
30 Correct 300 ms 377080 KB Output is correct
31 Correct 299 ms 376952 KB Output is correct
32 Correct 299 ms 377028 KB Output is correct
33 Correct 296 ms 377048 KB Output is correct
34 Correct 291 ms 377108 KB Output is correct
35 Correct 307 ms 377196 KB Output is correct
36 Correct 295 ms 376824 KB Output is correct
37 Correct 290 ms 376824 KB Output is correct
38 Correct 338 ms 377052 KB Output is correct
39 Correct 328 ms 377084 KB Output is correct
40 Correct 335 ms 377132 KB Output is correct
41 Correct 295 ms 376904 KB Output is correct
42 Correct 315 ms 376948 KB Output is correct
43 Correct 297 ms 376952 KB Output is correct
44 Correct 344 ms 377000 KB Output is correct
45 Correct 709 ms 433312 KB Output is correct
46 Correct 696 ms 433200 KB Output is correct
47 Correct 647 ms 433260 KB Output is correct
48 Correct 687 ms 433360 KB Output is correct
49 Correct 729 ms 433176 KB Output is correct
50 Correct 582 ms 433320 KB Output is correct
51 Correct 561 ms 433060 KB Output is correct
52 Correct 630 ms 433580 KB Output is correct
53 Correct 691 ms 428908 KB Output is correct
54 Correct 445 ms 428872 KB Output is correct
55 Correct 457 ms 429012 KB Output is correct
56 Correct 447 ms 428956 KB Output is correct
57 Correct 615 ms 432384 KB Output is correct
58 Correct 700 ms 432272 KB Output is correct
59 Correct 744 ms 436004 KB Output is correct
60 Correct 763 ms 434924 KB Output is correct
61 Correct 713 ms 434100 KB Output is correct
62 Correct 571 ms 435744 KB Output is correct
63 Correct 563 ms 434668 KB Output is correct
64 Correct 655 ms 434084 KB Output is correct
65 Correct 507 ms 430700 KB Output is correct
66 Correct 543 ms 430672 KB Output is correct
67 Correct 674 ms 430644 KB Output is correct
68 Correct 700 ms 430668 KB Output is correct
69 Correct 636 ms 432544 KB Output is correct
70 Correct 709 ms 432620 KB Output is correct
71 Correct 568 ms 428912 KB Output is correct
72 Correct 600 ms 429052 KB Output is correct
73 Correct 685 ms 429060 KB Output is correct
74 Correct 644 ms 428880 KB Output is correct
75 Correct 675 ms 433484 KB Output is correct
76 Correct 697 ms 433520 KB Output is correct
77 Correct 629 ms 433608 KB Output is correct
78 Correct 747 ms 433300 KB Output is correct
79 Correct 653 ms 433132 KB Output is correct
80 Correct 4502 ms 968468 KB Output is correct
81 Correct 4141 ms 968684 KB Output is correct
82 Correct 4393 ms 968732 KB Output is correct
83 Correct 4650 ms 968680 KB Output is correct
84 Correct 4515 ms 968688 KB Output is correct
85 Correct 2734 ms 968392 KB Output is correct
86 Correct 2641 ms 968860 KB Output is correct
87 Correct 3708 ms 941676 KB Output is correct
88 Correct 5284 ms 894684 KB Output is correct
89 Correct 2305 ms 895616 KB Output is correct
90 Correct 2222 ms 895708 KB Output is correct
91 Correct 2223 ms 895748 KB Output is correct
92 Correct 3899 ms 927452 KB Output is correct
93 Correct 4423 ms 927180 KB Output is correct
94 Correct 5397 ms 1004856 KB Output is correct
95 Correct 4612 ms 1007812 KB Output is correct
96 Correct 4740 ms 994320 KB Output is correct
97 Correct 3015 ms 1017440 KB Output is correct
98 Correct 3063 ms 1006056 KB Output is correct
99 Correct 3015 ms 994412 KB Output is correct
100 Correct 2840 ms 941428 KB Output is correct
101 Correct 2714 ms 940992 KB Output is correct
102 Correct 4485 ms 941368 KB Output is correct
103 Correct 4341 ms 941240 KB Output is correct
104 Correct 3934 ms 967460 KB Output is correct
105 Correct 3896 ms 967588 KB Output is correct
106 Correct 3316 ms 908764 KB Output is correct
107 Correct 3374 ms 908916 KB Output is correct
108 Correct 3702 ms 908864 KB Output is correct
109 Correct 3358 ms 908944 KB Output is correct
110 Correct 3569 ms 955816 KB Output is correct
111 Correct 3587 ms 955928 KB Output is correct
112 Correct 3629 ms 955676 KB Output is correct
113 Correct 4549 ms 983032 KB Output is correct
114 Correct 4687 ms 982988 KB Output is correct