제출 #129827

#제출 시각아이디문제언어결과실행 시간메모리
129827nikolapesic2802Port Facility (JOI17_port_facility)C++14
0 / 100
3 ms1144 KiB
#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=2e5+5;
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)
{
    a=find(a);
    b=find(b);
    if(a==b)
    {
        printf("0\n");
        exit(0);
    }
    par[a]=b;
}
const int mod=1e9+7;
int mul(int a,int b)
{
    return (ll)a*b%mod;
}
int powmod(int k,int x=2)
{
    int ans=1;
    for(;k;k>>=1,x=mul(x,x))
        if(k&1)
            ans=mul(ans,x);
    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());
        for(auto p:ok)
        {
            if(p.f<niz[i].s)
                merge(p.s,i);
            else
                break;
        }
        ok.insert({niz[i].s,i});
    }
    set<int> yes;
    for(int i=0;i<n;i++)
        yes.insert(find(i));
    printf("%i\n",powmod(yes.size()));
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp: In function 'int main()':
port_facility.cpp:60:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=0;i<N;i++)
     ^~~
port_facility.cpp:62:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  int n;
  ^~~
port_facility.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
port_facility.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i",&niz[i].f,&niz[i].s);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...