This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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) {}
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |