Submission #1209781

#TimeUsernameProblemLanguageResultExecution timeMemory
1209781Zbyszek99Port Facility (JOI17_port_facility)C++20
100 / 100
2082 ms86788 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace std; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; struct node { pii max_ = {-1e9,0}; pii min_ = {1e9,0}; node operator+(const node& other) { node res; res.max_ = max(max_,other.max_); res.min_ = min(min_,other.min_); return res; } }; const int tree_siz = 2048*2048-1; node drzewo[tree_siz+1]; node get_seg(int akt, int p1, int p2, int s1, int s2) { if(p2 < s1 || p1 > s2) return {{-1e9,0},{1e9,0}}; if(p1 >= s1 && p2 <= s2) return drzewo[akt]; return get_seg(akt*2,p1,(p1+p2)/2,s1,s2)+get_seg(akt*2+1,(p1+p2)/2+1,p2,s1,s2); } void upd(int v) { drzewo[v] = drzewo[v*2] + drzewo[v*2+1]; if(v != 1) upd(v/2); } void change(int l, int r, int ind, bool w = 0) { if(!w) { drzewo[tree_siz/2+1+l] = {{r,ind},{1e9,ind}}; drzewo[tree_siz/2+1+r] = {{-1e9,ind},{l,ind}}; } else { drzewo[tree_siz/2+1+l] = {{-1e9,ind},{1e9,ind}}; drzewo[tree_siz/2+1+r] = {{-1e9,ind},{1e9,ind}}; } upd((tree_siz/2+1+l)/2); upd((tree_siz/2+1+r)/2); } int L[1000'001]; int R[1000'001]; int ans[1000'001]; int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n; cin >> n; rep(i,n) { cin >> L[i] >> R[i]; ans[i] = -1; change(L[i],R[i],i); } ll ways = 1; rep(i,n) { if(ans[i] == -1) { ways *= 2; ways %= MOD; ans[i] = 0; change(L[i],R[i],i,1); queue<int> q; q.push(i); while(!q.empty()) { int t = q.front(); q.pop(); node seg = get_seg(1,0,tree_siz/2,L[t],R[t]); while(seg.max_.ff > R[t] || seg.min_.ff < L[t]) { int ind = seg.max_.ss; if(seg.min_.ff < L[t]) { ind = seg.min_.ss; } ans[ind] = ans[t] ^ 1; change(L[ind],R[ind],ind,1); seg = get_seg(1,0,tree_siz/2,L[t],R[t]); q.push(ind); } } } } vector<pii> sort_vert; rep(i,n) sort_vert.pb({L[i],i}); sort(all(sort_vert)); stack<int> st[2]; forall(it,sort_vert) { int v = it.ss; int b = ans[v]; while(siz(st[b]) > 0 && R[st[b].top()] < L[v]) { st[b].pop(); } if(siz(st[b]) != 0 && R[st[b].top()] < R[v]) { cout << "0\n"; return 0; } st[b].push(v); } cout << ways << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...