Submission #919020

#TimeUsernameProblemLanguageResultExecution timeMemory
919020efishelPort Facility (JOI17_port_facility)C++17
0 / 100
0 ms344 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...