Submission #27115

#	Time	Username	Problem	Language	Result	Execution time	Memory
27115		samir_droubi	Port Facility (JOI17_port_facility)	C++14	0 / 100	6 ms	65504 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];
bool vis[mxn];
int ans=1;
void dfs(int v,int p)
{
  vis[v]=true;
  for(int i=0;i<gr[v].size();++i)
  {
    int u=gr[v][i];
    if(vis[u])
    {
      if(u==p)continue;
      else ans=0;
    }
    else dfs(u,v);
  }
}
int main()
{
  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])continue;
    dfs(i,-1);
    ans*=2;
    ans%=mod;
  }
  printf("%d\n",ans);
  return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void dfs(int, int)':
port_facility.cpp:38:16: 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:71:11: warning: statement has no effect [-Wunused-value]
     for(it;it!=in.end()&&(it->first)<a[i].second;++it)
           ^
port_facility.cpp:51:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
port_facility.cpp:53: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