Submission #28209

#	Time	Username	Problem	Language	Result	Execution time	Memory
28209		top34051	Port Facility (JOI17_port_facility)	C++14	78 / 100	6000 ms	201120 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define mod 1000000007LL
#define inf 10000000
int n,bip;
int vis[maxn];
pair<int,int> p[maxn];
pair<int,int> tree[2][maxn*8];
void build(int now,int l,int r) {
    if(l==r) {
        tree[0][now] = tree[1][now] = {-inf,0};
        return ;
    }
    int mid = (l+r)/2;
    build(now<<1,l,mid); build(now<<1|1,mid+1,r);
    tree[0][now] = tree[1][now] = {-inf,0};
}
void update(int num,int now,int l,int r,int x,pair<int,int> val) {
    if(l>r || l>x || r<x) return ;
    if(l==r) {
        tree[num][now] = val;
        return ;
    }
    int mid = (l+r)/2;
    update(num,now<<1,l,mid,x,val); update(num,now<<1|1,mid+1,r,x,val);
    tree[num][now] = max(tree[num][now<<1],tree[num][now<<1|1]);
}
pair<int,int> query(int num,int now,int l,int r,int x,int y) {
    if(l>r || r<x || y<l) return {-inf,0};
    if(x<=l && r<=y) return tree[num][now];
    int mid = (l+r)/2;
    return max(query(num,now<<1,l,mid,x,y),query(num,now<<1|1,mid+1,r,x,y));
}
void dfs(int x,int col) {
    pair<int,int> t;
//    printf("dfs %d : %d\n",x,col);
    if(vis[x]==-1) vis[x] = col;
    else {
        update(0,1,1,2*n,p[x].first,{-inf,x});
        update(1,1,1,2*n,p[x].second,{-inf,x});
        if(vis[x]!=col) bip = 0;
    }
    while(1) {
        t = query(0,1,1,2*n,p[x].first,p[x].second);
//        printf("\tQ 0 [%d, %d] = {%d, %d}\n",p[x].first,p[x].second,t.first,t.second);
        if(t.first<=p[x].second) break;
//        printf("---- %d -> %d\n",x,t.second);
        dfs(t.second,!col);
    }
    while(1) {
        t = query(1,1,1,2*n,p[x].first,p[x].second);
//        printf("\tQ 1 [%d, %d] = {%d, %d}\n",p[x].first,p[x].second,t.first,t.second);
        if(-t.first>=p[x].first) break;
//        printf("---- %d -> %d\n",x,t.second);
        dfs(t.second,!col);
    }
}
void checkbip() {
    int i;
    pair<int,int> t;
    build(1,1,2*n);
    for(i=1;i<=n;i++) update(vis[i],1,1,2*n,p[i].first,{p[i].second,i});
    for(i=1;i<=n;i++) {
        t = query(vis[i],1,1,2*n,p[i].first,p[i].second);
        if(t.first>p[i].second) bip = 0;
    }
}
long long pow(long long x,int y) {
    if(y==0) return 1LL;
    if(y%2!=0) return (pow(x,y-1)*x)%mod;
    return pow((x*x)%mod,y/2);
}
main() {
    int i,cnt;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d%d",&p[i].first,&p[i].second);
    sort(&p[1],&p[n+1]);
    build(1,1,2*n);
    for(i=1;i<=n;i++) update(0,1,1,2*n,p[i].first,{p[i].second,i});
    for(i=1;i<=n;i++) update(1,1,1,2*n,p[i].second,{-p[i].first,i});
    bip = 1; cnt = 0;
    memset(vis,-1,sizeof(vis));
    for(i=1;i<=n;i++) if(vis[i]==-1) dfs(i,0), cnt++;
    checkbip();
    if(!bip) printf("0");
    else printf("%lld",pow(2LL,cnt));
}

Compilation message (stderr)

port_facility.cpp:74:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:76:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
port_facility.cpp:77:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%d%d",&p[i].first,&p[i].second);
                                                             ^

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