Submission #953473

#TimeUsernameProblemLanguageResultExecution timeMemory
953473pccPort Facility (JOI17_port_facility)C++17
22 / 100
2 ms860 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fs first #define sc second #define ll long long const ll mod = 1e9+7; const int mxn = 4024; ll pw(ll a,ll b){ ll re = 1; while(b){ if(b&1)re = re*a%mod; b>>=1; a = a*a%mod; } return re; } ll mad(ll a,ll b){ a += b; return a>=mod?a-mod:a; } void print(priority_queue<pii,vector<pii>,less<pii>> pq){ vector<pii> tmp; while(!pq.empty()){ cerr<<pq.top().fs<<','<<pq.top().sc<<' '; tmp.push_back(pq.top()); pq.pop(); } cerr<<endl; return; } struct DSU{ int dsu[mxn],sz[mxn]; priority_queue<pii,vector<pii>,less<pii>> pq[mxn]; DSU(){} void init(int n){ for(int i = 0;i<=n;i++)dsu[i] = i,sz[i] = 1; return; } int root(int k){ return k == dsu[k]?k:dsu[k] = root(dsu[k]); } void onion(int a,int b){ a = root(a),b = root(b); if(a == b)return; if(sz[a]<sz[b])swap(a,b); dsu[b] = a; sz[a] += sz[b]; if(pq[a].size()<pq[b].size())pq[a].swap(pq[b]); while(!pq[b].empty()){ pq[a].push(pq[b].top()); pq[b].pop(); } return; } }; pii arr[mxn]; int N; int C = 0; int col[mxn]; DSU dsu; int op[mxn]; set<pii> st; bitset<mxn> active; void update(int r){ r = dsu.root(r); if(!dsu.pq[r].empty()&&st.find(dsu.pq[r].top()) != st.end())st.erase(dsu.pq[r].top()); while(!dsu.pq[r].empty()&&!active[dsu.pq[r].top().sc])dsu.pq[r].pop(); if(!dsu.pq[r].empty())st.insert(dsu.pq[r].top()); return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N; dsu.init(N*2); for(int i = 1;i<=N;i++){ cin>>arr[i].fs>>arr[i].sc; op[arr[i].fs] = i; op[arr[i].sc] = -i; dsu.pq[i*2].push(pii(arr[i].fs,i)); } for(int i = 1;i<=N*2;i++){ if(op[i]>0){ active[op[i]] = true; update(op[i]*2); continue; } int pos = -op[i]; active[pos] = false; update(dsu.root(pos*2)); while(!st.empty()&&st.rbegin()->fs>arr[pos].fs){ if(active[st.rbegin()->sc]){ dsu.onion(pos*2-1,st.rbegin()->sc*2); dsu.onion(pos*2,st.rbegin()->sc*2-1); } st.erase(*st.rbegin()); } update(dsu.root(pos*2-1)); //cerr<<i<<":";for(auto &j:st)cerr<<j.fs<<','<<j.sc<<' ';cerr<<endl; } int ans = 0; for(int i = 1;i<=N;i++){ if(dsu.root(i*2) == dsu.root(i*2-1)){ cout<<0; return 0; } if(dsu.root(i*2) == i*2)ans++; if(dsu.root(i*2-1) == i*2-1)ans++; } cout<<pw(2,ans>>1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...