Submission #136670

#	Time	Username	Problem	Language	Result	Execution time	Memory
136670		Alliance	Port Facility (JOI17_port_facility)	C++14	22 / 100	6145 ms	940568 KiB

port_facility

// In the Name of Allah
#include<bits/stdc++.h>
#define double long double
typedef long long ll;
const ll MAX_N = 2e6+100;
const ll MOD = 1e9+7;
using namespace std;

vector<int> seg[MAX_N*3][2];
pair<int,int> lr[MAX_N];
int a[MAX_N];
int b[MAX_N];
int p[MAX_N];
vector<int> g[MAX_N];
vector<int> vc;
int mark[MAX_N];
int cl[MAX_N];
int n,cnt;

void no(){
    cout << 0;
    exit(0);
}

void dfs(int v){
    mark[v]++;
    for(auto x:g[v]){
        if (mark[x]){
            if (cl[x]==cl[v])
                no();
        }
        else{
            cl[x] = 3-cl[v];
            dfs(x);
        }
    }
}

void build(int k,int l,int r){
    if (l==r){
        if (a[l])
            seg[k][0].push_back(a[l]);
        if (b[l])
            seg[k][1].push_back(b[l]);
        return;
    }
    int mid = (l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    for(int i = 0;i<2;++i){
        int lc = k*2;
        int rc = lc+1;
        seg[k][i].resize(seg[lc][i].size()+seg[rc][i].size());
        merge(seg[lc][i].begin(),seg[lc][i].end(),seg[rc][i].begin(),seg[rc][i].end(),seg[k][i].begin());
    }
}

void ask(int l,int r,int a,int b,int k,int fl){
    if (r<a or b<l)
        return;
    if (a<=l and r<=b){
        if (fl==0){
            for(auto x:seg[k][0]){
                if (x>=a)
                    return;
                vc.push_back(x);
            }
        }
        else
        {
            for(int i = seg[k][1].size()-1;i>=0;--i){
                int x = seg[k][1][i];
                if (x<=b)
                    return;
                vc.push_back(x);
            }
        }
        return;
    }
    int mid = (l+r)/2;
    ask(l,mid,a,b,k*2,fl);
    ask(mid+1,r,a,b,k*2+1,fl);
}

int main()
{
    cin >> n;
    for(int i = 1;i<=n;++i)
        scanf("%d%d",&lr[i].first,&lr[i].second);
    for(int i = 1;i<=n;++i){
        b[lr[i].first] = lr[i].second;
        a[lr[i].second] = lr[i].first;
        p[lr[i].second] = p[lr[i].first] = i;
    }
    build(1,1,2*n);
    for(int i = 1;i<=n;++i){
        vc.clear();
        ask(1,2*n,lr[i].first,lr[i].second,1,0);
        if (vc.size()){
            sort(vc.begin(),vc.end());
            for(int j = 0;j<vc.size()-1;j++)
            {
                int x = vc[j];
                int y = vc[j+1];
                if (b[y]>b[x])
                    no();
            }
            for(auto x:vc)
                g[i].push_back(p[x]);
        }
        vc.clear();
        ask(1,2*n,lr[i].first,lr[i].second,1,1);
        if (vc.size()){
            sort(vc.begin(),vc.end());
            for(int j = 0;j<vc.size()-1;j++){
                int x = vc[j];
                int y = vc[j+1];
                if (a[y]>a[x])
                    no();
            }
        }
        for(auto x:vc)
            g[i].push_back(p[x]);
    }
    for(int i = 1;i<=n;++i){
        if (mark[i])
            continue;
        cnt++;
        dfs(i);
    }
    ll ans = 1;
    while(cnt--)
        ans *= 2,ans %= MOD;
    cout << ans;
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:101:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j<vc.size()-1;j++)
                           ~^~~~~~~~~~~~
port_facility.cpp:115:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j<vc.size()-1;j++){
                           ~^~~~~~~~~~~~
port_facility.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&lr[i].first,&lr[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22