제출 #28205

#제출 시각아이디문제언어결과실행 시간메모리
28205top34051Port Facility (JOI17_port_facility)C++14
0 / 100
0 ms138744 KiB
#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 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);
    }
}
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]);
    for(i=1;i<=2*n;i++) update(0,1,1,2*n,i,{-inf,0});
    for(i=1;i<=2*n;i++) update(1,1,1,2*n,i,{-inf,0});
    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++;
    if(!bip) printf("0");
    else printf("%lld",pow(2LL,cnt));
}

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

port_facility.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:57:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
port_facility.cpp:58: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);
                                                             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...