Submission #313288

#	Time	Username	Problem	Language	Result	Execution time	Memory
313288		edsa	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	384 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
const ll MOD = 1e9+7;
const int INF = 1e9+9;
const int MAXN = 1000006;


template <class T, class Oper>
struct LzySegTree {
    int n, h; vector<T> st;
    Oper op;

    LzySegTree(const vector<T> &A)
        : n(A.size()), h(sizeof(int)*8-__builtin_clz(n)),
          st(n<<1), op(*this) {
        copy(A.begin(), A.end(), st.begin()+n);
        build(0, n);
    }

    void build(int L, int R) {
        int len = 2;
        for (L += n, R += n-1; L > 1; len <<= 1) {
            L >>= 1, R >>= 1;
            for (int i = R; i >= L; --i) op.calc(i, len);
        }
    }

    void push(int L, int R) {
        int s = h, len = 1<<h;
        for (L += n, R += n-1; s > 0; --s, len >>= 1)
            for (int i = L >> s; i <= R >> s; ++i) op.pushDelOps(i, len);
    }

    void update(int L, int R, typename Oper::TUpd val) {
        push(L, L+1), push(R-1, R);
        int L0 = L, R0 = R, len = 1;
        for (L += n, R += n; L < R; L >>= 1, R >>= 1, len <<= 1) {
            if (L&1) op.updateOp(L++, len, val);
            if (R&1) op.updateOp(--R, len, val);
        }
        build(L0, L0+1), build(R0-1, R0);
    }

    T query(int L, int R) {
        push(L, L+1), push(R-1, R);
        T resl = op.identity, resr = op.identity;
        for (L += n, R += n; L < R; L >>= 1, R >>= 1) {
            if (L&1) resl = op.op(resl, st[L++]);
            if (R&1) resr = op.op(st[--R], resr);
        }
        return op.op(resl, resr);
    }

    void print() {
        for (int i = 0; i < n; ++i) {
            cerr << i << ": " << st[i] << " d(" << op.d[i] << endl;
        }
        for (int i = n; i < 2*n; ++i) {
            cerr << i << ": " << st[i] << endl;
        }
    }
};

template<int N>
struct GetSetEqClass {
    const int identity = 0;
    using TUpd = int;
    LzySegTree<int, GetSetEqClass> &st; vector<int> d;

    GetSetEqClass(LzySegTree<int, GetSetEqClass> &st) : st(st), d(st.n, -2) {}

    static inline int op(int a, int b) {
        if (a <= 0) return b;
        if (b <= 0) return a;
        return a != b? N+1 : a;
    }

    inline void calc(int p, int len) {
        st.st[p] = d[p] == -2? op(st.st[p<<1], st.st[p<<1|1]) : d[p];
    }

    inline void updateOp(int p, int len, int value) {
        if (value == -2) return;
        if (st.st[p] != -1 or value == 0) st.st[p] = value;
        if (p < st.n and d[p] != -1) d[p] = value;
    }

    inline void pushDelOps(int p, int len) {
        updateOp(p<<1, len>>1, d[p]);
        updateOp(p<<1|1, len>>1, d[p]);
        d[p] = -2;
    }
};

int n, a[MAXN], b[MAXN], e[MAXN], id[MAXN];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i]; --a[i], --b[i];
        e[a[i]] = -i;
        e[b[i]] = i;
    }

    LzySegTree<int, GetSetEqClass<2>> lst(vi(2*n));
    ll ans = 1;

    vi stack;
    for (int i = 0; i < 2*n; ++i) {
        // cerr << "stack\n";
        // for (int v : stack) {
        //     cerr << v << "-" << lst.query(id[v], id[v]+1) << " ";
        // }
        // cerr << endl;
        if (e[i] < 0) {
            id[-e[i]] = stack.size();
            stack.push_back(-e[i]);
        } else {
            int val = lst.query(id[e[i]]+1, stack.size());
            int cur = lst.query(id[e[i]], id[e[i]]+1);
        //     cerr << a[e[i]] << " " << b[e[i]] << ") ";
        //     cerr << cur << " " << val << endl;
            if (val <= 0) {
                if (cur == 0) {
                    lst.update(id[e[i]]+1, stack.size(), 1);
                    ans *= 2;
                    if (ans > MOD) ans -= MOD;
                } else {
                    // if (b[e[i]] == 7) {
                    //     lst.print();
                    // }
                    lst.update(id[e[i]]+1, stack.size(), cur == 1? 2 : 1);
                    // if (b[e[i]] == 7) {
                    //     lst.print();
                    // }
                    // cerr << id[e[i]]+1 << " " << stack.size() << " -- ";
                    // cerr << "sh " << lst.query(id[e[i]]+1, id[e[i]]+2) << endl;
                }
            } else if (val == 3 or val == cur) {
                ans = 0;
            } else {
                lst.update(id[e[i]]+1, stack.size(), val);
            }
            lst.update(id[e[i]], id[e[i]]+1, -1);
        }
        while(!stack.empty() and b[stack.back()] <= i) {
            stack.pop_back();
            lst.update(stack.size(), stack.size()+1, 0);
        }
    }
    cout << ans << endl;
}

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