Submission #919020

#	Time	Username	Problem	Language	Result	Execution time	Memory
919020		efishel	Port Facility (JOI17_port_facility)	C++17	0 / 100	0 ms	344 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MOD = 1E9+7;

#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
const ll IDEM = 1E18+16;
struct SegTree {
    struct Node {
        ll sum;
        ll minN;

        Node (ll val): minN(val), sum(1) {}

        Node (): minN(IDEM), sum(0) {}

        Node operator+ (const Node& o) {
            Node ans;
            ans.minN = min(minN, o.minN);
            ans.sum = sum + o.sum;
            return ans;
        }
    };
    vector <Node> tree;

    SegTree (ll n): tree(2*n, Node()) {}

    void pull (ll l, ll r, ll id) {
        tree[id] = tree[id+1] + tree[id+off];
    }

    void update (ll i, ll val, ll l, ll r, ll id) {
        if (r < i || i < l) return;
        if (l == r) {
            tree[id] = Node(val);
            return;
        }
        update(i, val, l, mid, id+1);
        update(i, val, mid+1, r, id+off);
        pull(l, r, id);
    }

    Node query (ll ql, ll qr, ll l, ll r, ll id) {
        if (qr < l || r < ql) return Node();
        if (ql <= l && r <= qr) return tree[id];
        return query(ql, qr, l, mid, id+1) + query(ql, qr, mid+1, r, id+off);
    }
};

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n;
    cin >> n;
    vector <pair <ll, ll> > ve;
    for (ll i = 0; i < n; i++) {
        ll th1, th2;
        cin >> th1 >> th2;
        th1--; th2--;
        ve.push_back({ th1, th2 });
    }
    sort(ve.begin(), ve.end());
    SegTree st(2*n);
    ll ans = 1;
    for (auto ppair : ve) {
        ll l = ppair.first, r = ppair.second;
        SegTree::Node th = st.query(l, r, 0, 2*n-1, 0);
        if (th.sum > 1) {
            cout << "0\n";
            return 0;
        }
        if (th.minN > l) ans = 2*ans % MOD;
        st.update(r, l, 0, 2*n-1, 0);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In constructor 'SegTree::Node::Node(ll)':
port_facility.cpp:14:12: warning: 'SegTree::Node::minN' will be initialized after [-Wreorder]
   14 |         ll minN;
      |            ^~~~
port_facility.cpp:13:12: warning:   'll SegTree::Node::sum' [-Wreorder]
   13 |         ll sum;
      |            ^~~
port_facility.cpp:16:9: warning:   when initialized here [-Wreorder]
   16 |         Node (ll val): minN(val), sum(1) {}
      |         ^~~~
port_facility.cpp: In constructor 'SegTree::Node::Node()':
port_facility.cpp:14:12: warning: 'SegTree::Node::minN' will be initialized after [-Wreorder]
   14 |         ll minN;
      |            ^~~~
port_facility.cpp:13:12: warning:   'll SegTree::Node::sum' [-Wreorder]
   13 |         ll sum;
      |            ^~~
port_facility.cpp:18:9: warning:   when initialized here [-Wreorder]
   18 |         Node (): minN(IDEM), sum(0) {}
      |         ^~~~

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