이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
const int N=2e6+5,mod=1e9+7;
vector<int> par(N);
int find(int tr)
{
if(par[tr]==tr)
return tr;
return par[tr]=find(par[tr]);
}
void merge(int a,int b)
{
par[find(a)]=find(b);
}
int powmod(int k,int x=2)
{
int ans=1;
for(;k;k>>=1,x=(ll)x*x%mod)
if(k&1)
ans=(ll)ans*x%mod;
return ans;
}
int main()
{
for(int i=0;i<N;i++)
par[i]=i;
int n;
scanf("%i",&n);
vector<pair<int,int> > niz(n);
for(int i=0;i<n;i++)
scanf("%i %i",&niz[i].f,&niz[i].s);
sort(all(niz));
set<pair<int,int> > ok;
for(int i=0;i<n;i++)
{
while(ok.size()&&(*ok.begin()).f<niz[i].f)
ok.erase(ok.begin());
auto it=ok.upper_bound({niz[i].s,n});
int cnt=0;
if(it!=ok.begin())
for(it--;;it--)
{
cnt++;
merge(i,(*it).s+n),merge(i+n,(*it).s);
if(it==ok.begin())
break;
}
for(int i=2;i<cnt;i++)
ok.erase(ok.begin());
ok.insert({niz[i].s,i});
}
for(int i=0;i<n;i++)
if(find(i)==find(i+n))
{
printf("0\n");
return 0;
}
int ans=0;
for(int i=0;i<2*n;i++)
if(find(i)==i)
ans++;
printf("%i\n",powmod(ans/2));
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp: In function 'int main()':
port_facility.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
51 | scanf("%i",&n);
| ~~~~~^~~~~~~~~
port_facility.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
54 | scanf("%i %i",&niz[i].f,&niz[i].s);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |