제출 #27117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
27117		samir_droubi	Port Facility (JOI17_port_facility)	C++14	0 / 100	3 ms	68432 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
int n;
const int mxn=(1e6)+5;
pair<int,int>a[mxn];

int st[mxn*8];
int mod=(1e9)+7;
void update(int p,int l,int r,int i)
{
  if(l==r)
  {
    ++st[p];
    return;  
  }
  int md=(l+r)/2;
  if(i<=md)update(p*2,l,md,i);
  else update(p*2+1,md+1,r,i);
  st[p]=st[p*2]+st[p*2+1];
}
int sum(int p,int l,int r,int i,int j)
{
  if(r<i||l>j)return 0;
  if(l>=i&&r<=j)return st[p];
  int md=(l+r)/2;
  int x=sum(p*2,l,md,i,j);
  int y=sum(p*2+1,md+1,r,i,j);
  return x+y;
}

map<int,int>in;
vector<int>gr[mxn];
int vis[mxn];
int ans=1;
queue<int>q;
void bfs()
{
  while(!q.empty())
  {
    int v=q.front();
    q.pop();
    for(int i=0;i<gr[v].size();++i)
    {
      int u=gr[v][i];
      if(vis[v]==vis[u])
        ans=0;
      if(vis[u]==-1)
      {
        vis[u]=1-vis[v];
        q.push(u);
      }
    }
  }
}
int main()
{
  memset(vis,-1,sizeof vis);

  scanf("%d",&n);
  for(int i=1;i<=n;++i)
    scanf("%d%d",&a[i].first,&a[i].second);
  sort(a+1,a+n+1);

  int m=0;
  for(int i=1;i<=n;++i)
  {
    m+=sum(1,1,2*n,a[i].first,a[i].second);
    update(1,1,2*n,a[i].second);
  }

  if(m>=n)
  {
    puts("0");
    return 0;
  }
  for(int i=1;i<=n;++i)
  {
    map<int,int>::iterator it=in.lower_bound(a[i].first);
    for(it;it!=in.end()&&(it->first)<a[i].second;++it)
    {
      gr[i].push_back(it->second);
      gr[it->second].push_back(i);
    }
    in[a[i].second]=i;
  }

  for(int i=1;i<=n;++i)
  {
    if(vis[i]!=-1)continue;
    vis[i]=0;
    q.push(i);
    bfs();
    ans*=2;
    ans%=mod;
  }
  printf("%d\n",ans);
  return 0;
}

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

port_facility.cpp: In function 'void bfs()':
port_facility.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[v].size();++i)
                  ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:79:11: warning: statement has no effect [-Wunused-value]
     for(it;it!=in.end()&&(it->first)<a[i].second;++it)
           ^
port_facility.cpp:59:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
port_facility.cpp:61:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&a[i].first,&a[i].second);
                                           ^

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