Submission #45567

#	Time	Username	Problem	Language	Result	Execution time	Memory
45567		kuzmichev_dima	Port Facility (JOI17_port_facility)	C++14	0 / 100	3 ms	700 KiB

port_facility

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>

using namespace std;

#define INF 1e+9
#define mp make_pair
#define pb push_back
#define fi first
#define fs first
#define se second
#define i64 long long
#define li long long
#define lint long long
#define pii pair<int, int>
#define vi vector<int>

#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++)

#define MAX_FLAG 0
#define MIN_FLAG 1

const int MOD = 1e9+7;
const int maxn = 1e6+5;
const int inf = 1e9;

typedef int Tree[maxn * 8];

int s[maxn];
int f[maxn];
int inits[maxn];
int initf[maxn];
int n;
set<int> untouched, in_process;
Tree tree_max, tree_min;
int s_pos_to_i[2 * maxn];
int f_pos_to_i[2 * maxn];

int select_max(int fi, int se) {
    if (fi == -1)
        return se;
    if (se == -1)
        return fi;
    return f[fi] > f[se] ? fi : se;
}

int select_min(int fi, int se) {
    if (fi == -1)
        return se;
    if (se == -1)
        return fi;
    //printf("select min %d %d\n", fi, se);
    return s[fi] < s[se] ? fi : se;
}

int get(const Tree& tree, int i, int L, int R, int A, int B, bool flag) {
    //printf("get i = %d L = %d R = %d A = %d B = %d\n", i, L, R, A, B);
    if (L >= B || A >= R)
        return -1;
    if (L >= A && R <= B)
        return tree[i];
    int M = (L + R) / 2;
    int g1 = get(tree, 2 * i, L, M, A, B, flag);
    int g2 = get(tree, 2 * i + 1, M, R, A, B, flag);
    return flag == MAX_FLAG ? select_max(g1, g2) : select_min(g1, g2);
}

void upd(Tree& tree, int i, int L, int R, int pos, bool flag) {
    if (L + 1 == R) {
        tree[i] = -1;
        return;
    }
    int M = (L + R) / 2;
    if (pos < M)
        upd(tree,i * 2, L, M, pos, flag);
    else upd(tree, i * 2 + 1, M, R, pos, flag);
    tree[i] = (flag == MIN_FLAG ? select_min(tree[i * 2], tree[i * 2 + 1]) : select_max(tree[i * 2], tree[i * 2 + 1]));
}

void add(int num) {
    untouched.erase(num);
    in_process.insert(num);
    upd(tree_max, 1, 0, 2 * n, s[num], MAX_FLAG);
    upd(tree_min, 1, 0, 2 * n, f[num], MIN_FLAG);
    f[num] = -inf;
    s[num] = inf;
}

void build(Tree& tree, int i, int L, int R, bool flag) {
    // printf("build i = %d L = %d R = %d\n", i, L, R);
    if (L + 1 == R) {
        tree[i] = flag == MIN_FLAG ? f_pos_to_i[L] : s_pos_to_i[L];
        return;
    }
    int M = (L + R) / 2;
    build(tree, 2 * i, L, M, flag);
    build(tree, 2 * i + 1, M, R, flag);
    tree[i] = (flag == MIN_FLAG ? select_min(tree[i * 2], tree[i * 2 + 1]) : select_max(tree[i * 2], tree[i * 2 + 1]));
}

int main() {
#ifdef LOCAL
    freopen("inp", "r", stdin);
    //freopen("outp", "w", stdout);
#else
    // freopen(TASKNAME ".in", "r", stdin);
    // freopen(TASKNAME ".out", "w", stdout);
#endif
    scanf("%d", &n);
    forn(i, n) {
        scanf("%d%d", &s[i], &f[i]);
        --s[i];
        --f[i];
        inits[i] = s[i];
        initf[i] = f[i];
        //printf("s[%d] =%d f[%d] = %d\n", i, s[i], i, f[i]);
    }
    forn(i, n)
        untouched.insert(i);
    forn(i, 2 * n) {
        f_pos_to_i[i] = s_pos_to_i[i] = -1;
    }
    forn(i, n) {
        f_pos_to_i[f[i]] = i;
        s_pos_to_i[s[i]] = i;
    }
    build(tree_min, 1, 0, 2 * n, MIN_FLAG);
    build(tree_max, 1, 0, 2 * n, MAX_FLAG);
    int ans = 1;
    /*forn(i, n) {
        printf("s[%d] = %d f[%d] = %d\n", i, s[i], i, f[i]);
    }*/
    while(!untouched.empty()) {
        int start = *untouched.begin();
        //printf("\n================\n");
        //printf("start = %d\n", start);
        ans = ans * 2 % MOD;
        add(start);
        while(!in_process.empty()) {
            int x = *in_process.begin();
            //printf("x = %d [%d; %d]\n", x, inits[x], initf[x]);
            in_process.erase(in_process.begin());
            while(true) {
                int next = get(tree_max, 1, 0, 2 * n, inits[x] + 1, initf[x], MAX_FLAG);
                //printf("next = %d\n", next);
                if (next == -1 || f[next] < initf[x])
                    break;
                add(next);
            }
            while(true) {
                int next = get(tree_min, 1, 0, 2 * n, inits[x] + 1, initf[x], MIN_FLAG);
                if (next == -1 || s[next] > inits[x])
                    break;
                add(next);
            }
        }
    }
    printf("%d", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &s[i], &f[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22