Submission #45582

#	Time	Username	Problem	Language	Result	Execution time	Memory
45582		kuzmichev_dima	Port Facility (JOI17_port_facility)	C++14	100 / 100	5715 ms	153696 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>
#include <unordered_set>

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;
unordered_set<int> in_process;
Tree tree_max, tree_min;
int s_pos_to_i[2 * maxn];
int f_pos_to_i[2 * maxn];
int color[maxn];
int undef;

inline int select_max(int fi, int se) {
    return f[fi] > f[se] ? fi : se;
}

inline int select_min(int fi, int 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 undef;
    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] = undef;
        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]));
}

inline void add(int 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]));
}

struct Event {
    int num, x, typ;
};

bool operator < (Event first, Event second) {
    return first.x < second.x;
}

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);
    undef = n;
    s[undef] = inf;
    f[undef] = -inf;
    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, 2 * n) {
        f_pos_to_i[i] = s_pos_to_i[i] = undef;
    }
    forn(i, n) {
        f_pos_to_i[f[i]] = i;
        s_pos_to_i[s[i]] = i;
    }
    forn(i, n)
        color[i] = 2;
    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]);
    }*/
    int start = 0;
    while(true) {
        while(start < n && color[start] != 2)
            ++start;
        if (start == n)
            break;
        //printf("\n================\n");
        //printf("start = %d\n", start);
        ans = ans * 2 % MOD;
        color[start] = 0;
        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 == undef || f[next] < initf[x])
                    break;
                color[next] = 1 - color[x];
                add(next);
            }
            while(true) {
                int next = get(tree_min, 1, 0, 2 * n, inits[x] + 1, initf[x], MIN_FLAG);
                if (next == undef || s[next] > inits[x])
                    break;
                color[next] = 1 - color[x];
                add(next);
            }
        }
    }
    vector<Event> events;
    forn(i, n) {
        events.pb({i, inits[i], 1});
        events.pb({i, initf[i], -1});
    }
    sort(events.begin(), events.end());
    set<int> S[2];
/*    forn(i, n)
        printf("color[%d] = %d\n", i, color[i]);*/
    for (const Event& event : events) {
        //printf("event x = %d num = %d typ = %d\n", event.x, event.num, event.typ);
        if (event.typ == 1) {
            if (!S[color[event.num]].empty()) {
                //printf("begin = %d\n", *S[1 - color[event.num]].begin());
                if (*S[color[event.num]].begin() < initf[event.num]) {
                    printf("0");
                    exit(0);
                }
            }
            S[color[event.num]].insert(initf[event.num]);
        } else {
            S[color[event.num]].erase(initf[event.num]);
        }
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:126: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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22