提交记录 3661


用户 题目 状态 得分 用时 内存 语言 代码长度
test_tset noi17f. 【NOI2017】分身术 Accepted 100 1.111 s 6200 KB C++11 17.20 KB
提交时间 评测时间
2018-07-17 22:53:47 2020-07-31 21:22:14
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<vector>
#include<map>
#include<set>
using namespace std;
const double eps=1e-9;
long long ans;
const int inf=1e9+9;
int xx,yy,mx,my;
struct segment
{
    int id_layer,l,r;
    bool operator <(const segment &temp)const
    {
        return l<temp.l;
    }
};
vector<segment>sg[101];
segment tc[101000],nw[101000];
int cnt_tc,cnt_nw;
segment now;
struct point
{
    int x,y,id;
    bool operator <(const point &temp)const
    {
       if(abs(1LL*(y-yy)*(temp.x-xx)-1LL*(x-xx)*(temp.y-yy))==0)
          return abs(x-xx)+abs(y-yy)>abs(temp.x-xx)+abs(temp.y-yy);
       return 1LL*(y-yy)*(temp.x-xx)-1LL*(x-xx)*(temp.y-yy)<0;
    }
};
point pt[101000],tmp[101000];
int num_layer;
int at[101000],as[101000],us[101000];
vector<int>vec[111];
int iu[101000],cnt_u;
vector<long long>sum[111];
int n,m,list[111];
int vis[101000],times,cnt,k;
long long tot;
void init()
{
    int i,j,s,p,q,id,inx,iny,id1,id2;
    times++;
    memset(at,-1,sizeof(at)); 
    my=mx=1e8+5;
    for(num_layer=0;num_layer<=100;num_layer++)
    {
        vec[num_layer].clear();
        cnt=0;
        for(i=0;i<n;i++)
        {
            if(vis[i]!=times)
                tmp[cnt++]=pt[i];
        }
        if(cnt==0)
           return;
        inx=inf;
        for(i=0;i<cnt;i++)
        {
            if(inx>tmp[i].x||(inx==tmp[i].x&&iny>tmp[i].y))
            {
                inx=tmp[i].x;
                iny=tmp[i].y;
				id=i;
            }
        }
        swap(tmp[0],tmp[id]);
        xx=tmp[0].x;
        yy=tmp[0].y;
        sort(tmp+1,tmp+cnt);
        for(i=0;i<cnt;i++)
        {
            while(vec[num_layer].size()>=2)
            {
                id1=vec[num_layer][vec[num_layer].size()-2];
                id2=vec[num_layer][vec[num_layer].size()-1];
                id=tmp[i].id;
                if(1LL*(pt[id].y-pt[id1].y)*(pt[id2].x-pt[id1].x)<1LL*(pt[id2].y-pt[id1].y)*(pt[id].x-pt[id1].x))
                    vec[num_layer].pop_back();
                else
                    break;
            }
            vec[num_layer].push_back(tmp[i].id);
        }
        double theta[2];
        int flag=0;
        for(i=0;i<vec[num_layer].size();i++)
        {
             id1=vec[num_layer][i];
             id2=vec[num_layer][(i+1)%vec[num_layer].size()];
             theta[1-flag]=atan2(pt[id2].y-pt[id1].y,pt[id2].x-pt[id1].x);
             if(i>0&&theta[1-flag]<theta[flag]-1e-9)
                 break;
             flag^=1;
        }
        cnt_u=0;
        if(i<vec[num_layer].size())
        {
            for(j=i;j<vec[num_layer].size();j++)
                iu[cnt_u++]=vec[num_layer][j];
            for(j=0;j<i;j++)
                iu[cnt_u++]=vec[num_layer][j];
            for(j=0;j<vec[num_layer].size();j++)
                vec[num_layer][j]=iu[j];
        }
        if(vec[num_layer].size()>=3)
        {
        	flag=0;
        	int nn=0;
            for(i=0;i<vec[num_layer].size();i++)
            {
                 id1=vec[num_layer][i];
                 id2=vec[num_layer][(i+1)%vec[num_layer].size()];
                 theta[1-flag]=atan2(pt[id2].y-pt[id1].y,pt[id2].x-pt[id1].x);
                 if(i==0||fabs(theta[1-flag]-theta[flag])>eps)
                 	vec[num_layer][nn++]=vec[num_layer][i];
                 flag^=1;
	    	}
	    	while(vec[num_layer].size()>nn)
	    	   vec[num_layer].pop_back();
	    }
		for(i=0;i<vec[num_layer].size();i++)
        {
             vis[vec[num_layer][i]]=times;
             at[vec[num_layer][i]]=num_layer;
             as[vec[num_layer][i]]=i;
        }
        sum[num_layer].clear();
        sum[num_layer].push_back(0); 
        for(i=0;i<vec[num_layer].size();i++)
        {
            id1=vec[num_layer][i];
            id2=vec[num_layer][(i+1)%vec[num_layer].size()];
            sum[num_layer].push_back(1LL*(pt[id2].y-my)*(pt[id1].x-mx)-1LL*(pt[id2].x-mx)*(pt[id1].y-my));
            sum[num_layer][i+1]+=sum[num_layer][i];
        }
        if(num_layer==0)
            tot=sum[num_layer].back();
    }
}
bool cmp(int id1,int id2)
{ 
    if(at[id1]==at[id2])
       return as[id1]<as[id2];
    return at[id1]<at[id2];
}
void got(int id_layer,int id1,int id2)
{
	int i,j,s,p,q,low,high,mid,md,cd,ip1,ip2,ie1,ie2,ll,rr,sz,lx,rx,iq1,iq2,u,v,cmft=0;
	double theta,alpha;
	bool ok=false,eq=false,gong_xian=false;
	if(sg[id_layer+1].size()==0)
	   return;
	sz=sg[id_layer+1].size();
    ie1=sg[id_layer+1][0].id_layer;
    ll=sg[id_layer+1][0].l;
    iq1=vec[ie1][ll]; 
	ie2=sg[id_layer+1].back().id_layer;
	rr=sg[id_layer+1].back().r;
	iq2=vec[ie2][rr];
	u=sg[id_layer+1].size()-1;
	v=sg[id_layer+1][u].r; 
	int cx,cy,dis=-inf;
	while(true)
	{
	     if(1LL*(pt[iq1].y-pt[id1].y)*(pt[iq2].x-pt[id1].x)!=1LL*(pt[iq1].x-pt[id1].x)*(pt[iq2].y-pt[id1].y))
		    goto orz;
		  eq=true;
		  for(v=sg[id_layer+1][u].r-1;v>=sg[id_layer+1][u].l;v--)
          {
          	 ie1=sg[id_layer+1][u].id_layer;
         	 iq1=vec[ie1][v+1];
         	 iq2=vec[ie1][v];
             if(1LL*(pt[iq1].y-pt[id1].y)*(pt[iq2].x-pt[id1].x)!=1LL*(pt[iq1].x-pt[id1].x)*(pt[iq2].y-pt[id1].y))
                 goto orz;
		  }
 		  for(v=sg[id_layer+1][u].r;v>=sg[id_layer+1][u].l;v--)
		  {
  			   ie1=sg[id_layer+1][u].id_layer;
  			   ip1=vec[ie1][v];
  			   if(dis<abs(pt[ip1].x-pt[id1].x)+abs(pt[ip1].y-pt[id1].y))
  			   {
   			  	  dis=abs(pt[ip1].x-pt[id1].x)+abs(pt[ip1].y-pt[id1].y);
   			  	  cx=u;
   			  	  cy=v;
   			   }
  		   }
		  ie1=sg[id_layer+1][u].id_layer;
		  iq1=vec[ie1][sg[id_layer+1][u].l];
 		  u=(u-1+sg[id_layer+1].size())%sg[id_layer+1].size();
 		  ie2=sg[id_layer+1][u].id_layer;
 		  v=sg[id_layer+1][u].r;
 		  iq2=vec[ie2][sg[id_layer+1][u].r];
 		  if(1LL*(pt[iq1].y-pt[id1].y)*(pt[iq2].x-pt[id1].x)!=1LL*(pt[iq1].x-pt[id1].x)*(pt[iq2].y-pt[id1].y))
              goto orz; 
		  if(u+1==sg[id_layer+1].size())
		  {
 		 	 gong_xian=true;
 		     break;
		  }
	}
	orz: 
	cmft+=gong_xian;
	int lm,rm;
	if(v==sg[id_layer+1][u].r)
	{
		u=(u+1)%sg[id_layer+1].size();
		v=sg[id_layer+1][u].l;
		lm=v;
		rm=v;
	}
	else
	{
		lm=sg[id_layer+1][u].l;
		rm=v+1;
	}
	low=u;
	high=u+sz-1; 
	while(low<=high)
	{
		mid=(low+high)>>1;
		ie1=sg[id_layer+1][mid%sz].id_layer;
		ll=sg[id_layer+1][mid%sz].r;
		ie2=sg[id_layer+1][(mid+1)%sz].id_layer;
		rr=sg[id_layer+1][(mid+1)%sz].l;
		ip1=vec[ie1][ll];
		ip2=vec[ie2][rr];
		ok=false;
	    if(1LL*(pt[ip1].y-pt[id1].y)*(pt[ip2].x-pt[id1].x)<1LL*(pt[ip1].x-pt[id1].x)*(pt[ip2].y-pt[id1].y))
  	      ok=true;
		if(1LL*(pt[iq1].y-pt[id1].y)*(pt[iq2].x-pt[id1].x)>1LL*(pt[iq1].x-pt[id1].x)*(pt[iq2].y-pt[id1].y))
		{ 
			  if(ok)
			  {
  				 if(1LL*(pt[ip1].y-pt[id1].y)*(pt[iq1].x-pt[id1].x)>=1LL*(pt[ip1].x-pt[id1].x)*(pt[iq1].y-pt[id1].y))
  				     ok=false;
		   	  }
  		 
		}
		else if(1LL*(pt[iq1].y-pt[id1].y)*(pt[iq2].x-pt[id1].x)<1LL*(pt[iq1].x-pt[id1].x)*(pt[iq2].y-pt[id1].y))
		{
			 if(!ok)
			 {
 			     if(1LL*(pt[ip1].y-pt[id1].y)*(pt[iq1].x-pt[id1].x)>1LL*(pt[ip1].x-pt[id1].x)*(pt[iq1].y-pt[id1].y))
 			       ok=true;
			 }
		}
		if(ok)
		   high=mid-1;
        else
           low=mid+1;
	}
	lx=low%sg[id_layer+1].size();
	if(eq&&lx==u&&1LL*(pt[iq1].y-pt[id1].y)*(pt[iq2].x-pt[id1].x)<1LL*(pt[iq1].x-pt[id1].x)*(pt[iq2].y-pt[id1].y))
		ll=rm;
	else
	{
    	if(lx==u&&eq)
    	{
    		low=lm;
    		high=rm;
    	}
    	else
    	{
     		low=sg[id_layer+1][lx].l;
	        high=sg[id_layer+1][lx].r;
    	}
    	while(low<=high)
    	{
    		mid=(low+high)>>1;
        	ie1=sg[id_layer+1][lx].id_layer;	
    		ip1=vec[ie1][mid];
    		if(mid==sg[id_layer+1][lx].r)
    		{
    			ie2=sg[id_layer+1][(lx+1)%sg[id_layer+1].size()].id_layer;
    			ll=sg[id_layer+1][(lx+1)%sg[id_layer+1].size()].l;
    			ip2=vec[ie2][ll];
    		}
    		else
    		    ip2=vec[ie1][mid+1];
	    	ok=false;
            if(1LL*(pt[ip1].y-pt[id1].y)*(pt[ip2].x-pt[id1].x)<1LL*(pt[ip1].x-pt[id1].x)*(pt[ip2].y-pt[id1].y))
	            ok=true; 
		    if(1LL*(pt[iq1].y-pt[id1].y)*(pt[iq2].x-pt[id1].x)>1LL*(pt[iq1].x-pt[id1].x)*(pt[iq2].y-pt[id1].y))
	    	{
	   		    if(ok)
			    {
  			    	 if(1LL*(pt[ip1].y-pt[id1].y)*(pt[iq1].x-pt[id1].x)>=1LL*(pt[ip1].x-pt[id1].x)*(pt[iq1].y-pt[id1].y))
  				         ok=false;
  		        }
	    	}
	    	else if(1LL*(pt[iq1].y-pt[id1].y)*(pt[iq2].x-pt[id1].x)<1LL*(pt[iq1].x-pt[id1].x)*(pt[iq2].y-pt[id1].y))
	    	{
	    		 if(!ok)
	    		 {
 	    		     if(1LL*(pt[ip1].y-pt[id1].y)*(pt[iq1].x-pt[id1].x)>1LL*(pt[ip1].x-pt[id1].x)*(pt[iq1].y-pt[id1].y))
 	    		       ok=true;
	    		 }
    		}
	    	if(ok)
	    	   high=mid-1;
            else
              low=mid+1;
    	}
    	ll=low;
	} 
	if(gong_xian)
	{
		lx=cx;
		ll=cy;
	}
	else
	{
		if(eq)
		{ 
			if(1LL*(pt[iq1].y-pt[id1].y)*(pt[iq2].x-pt[id1].x)<1LL*(pt[iq1].x-pt[id1].x)*(pt[iq2].y-pt[id1].y))
			{
				lx=u;
				ll=rm;
			}
		}
	}
    ie1=sg[id_layer+1][lx].id_layer;
	if(ll>sg[id_layer+1][lx].r)
	{
		lx=(lx+1)%sg[id_layer+1].size();
		ll=sg[id_layer+1][lx].l;
		ie1=sg[id_layer+1][lx].id_layer;
	}
	ip1=vec[ie1][ll];	
    if(1LL*(pt[ip1].y-pt[id1].y)*(pt[id2].x-pt[id1].x)>1LL*(pt[ip1].x-pt[id1].x)*(pt[id2].y-pt[id1].y))
        return;            
    low=0;
	high=sg[id_layer+1].size()-1;
	sz=sg[id_layer+1].size();
	
	int lq;
    ie1=sg[id_layer+1][0].id_layer;
    lq=sg[id_layer+1][0].l;
    iq1=vec[ie1][lq]; 
	ie2=sg[id_layer+1].back().id_layer;
	rr=sg[id_layer+1].back().r;
	iq2=vec[ie2][rr];
	u=sg[id_layer+1].size()-1;
	v=sg[id_layer+1][u].r;
	eq=false;
	gong_xian=false;
	dis=-inf;
	while(true)
	{
	     if(1LL*(pt[iq1].y-pt[id2].y)*(pt[iq2].x-pt[id2].x)!=1LL*(pt[iq1].x-pt[id2].x)*(pt[iq2].y-pt[id2].y))
		    goto oz;
		 eq=true;
         for(v=sg[id_layer+1][u].r-1;v>=sg[id_layer+1][u].l;v--)
         {
         	ie1=sg[id_layer+1][u].id_layer;
         	iq1=vec[ie1][v+1];
         	iq2=vec[ie1][v];
            if(1LL*(pt[iq1].y-pt[id2].y)*(pt[iq2].x-pt[id2].x)!=1LL*(pt[iq1].x-pt[id2].x)*(pt[iq2].y-pt[id2].y))
                goto oz;
         }
          for(v=sg[id_layer+1][u].r;v>=sg[id_layer+1][u].l;v--)
	     {
  			   ie1=sg[id_layer+1][u].id_layer;
  			   ip1=vec[ie1][v];
  			   if(dis<abs(pt[ip1].x-pt[id2].x)+abs(pt[ip1].y-pt[id2].y))
  			   {
   			  	  dis=abs(pt[ip1].x-pt[id2].x)+abs(pt[ip1].y-pt[id2].y);
   			  	  cx=u;
   			  	  cy=v;
   			   }
  		   }
		 ie1=sg[id_layer+1][u].id_layer;
		 iq1=vec[ie1][sg[id_layer+1][u].l];
 		 u=(u-1+sg[id_layer+1].size())%sg[id_layer+1].size();
 		 ie2=sg[id_layer+1][u].id_layer;
 		 iq2=vec[ie2][sg[id_layer+1][u].r];
 		 v=sg[id_layer+1][u].r; 
 		 if(1LL*(pt[iq1].y-pt[id2].y)*(pt[iq2].x-pt[id2].x)!=1LL*(pt[iq1].x-pt[id2].x)*(pt[iq2].y-pt[id2].y))
              goto oz; 
		  if(u+1==sg[id_layer+1].size())
		  {
  		 	 gong_xian=true;
 		     break;
		  }
	}
	oz:
	cmft+=gong_xian;
	if(cmft==2&&id1!=id2)
	{
		 ie1=sg[id_layer+1][lx].id_layer;
	  	 ip1=vec[ie1][ll];
	      if(1LL*(pt[ip1].y-pt[id1].y)*(pt[id2].x-pt[id1].x)==1LL*(pt[ip1].x-pt[id1].x)*(pt[id2].y-pt[id1].y))
            return;	 
	}
	if(v==sg[id_layer+1][u].r)
	{
		u=(u+1)%sg[id_layer+1].size();
		v=sg[id_layer+1][u].l;
		lm=v;
		rm=v; 
	}
	else
	{
		lm=sg[id_layer+1][u].l;
		rm=v+1;
	}
	low=u;
	high=u+sz-1;
	while(low<=high)
	{
		mid=(low+high)>>1;
    	ie1=sg[id_layer+1][mid%sz].id_layer;
    	int lq;
		lq=sg[id_layer+1][mid%sz].r;
		ie2=sg[id_layer+1][(mid+1)%sz].id_layer;
		rr=sg[id_layer+1][(mid+1)%sz].l;
		ip1=vec[ie1][lq];
		ip2=vec[ie2][rr];
		ok=false;
	    if(1LL*(pt[ip1].y-pt[id2].y)*(pt[ip2].x-pt[id2].x)<=1LL*(pt[ip1].x-pt[id2].x)*(pt[ip2].y-pt[id2].y))
  	      ok=true;
		if(1LL*(pt[iq1].y-pt[id2].y)*(pt[iq2].x-pt[id2].x)>1LL*(pt[iq1].x-pt[id2].x)*(pt[iq2].y-pt[id2].y))
		{
			  if(ok)
			  {
  				 if(1LL*(pt[ip1].y-pt[id2].y)*(pt[iq1].x-pt[id2].x)<1LL*(pt[ip1].x-pt[id2].x)*(pt[iq1].y-pt[id2].y))
  				     ok=false;
  			  }
		}
		else if(1LL*(pt[iq1].y-pt[id2].y)*(pt[iq2].x-pt[id2].x)<1LL*(pt[iq1].x-pt[id2].x)*(pt[iq2].y-pt[id2].y))
		{
			 if(!ok)
			 {
 			     if(1LL*(pt[ip1].y-pt[id2].y)*(pt[iq1].x-pt[id2].x)<=1LL*(pt[ip1].x-pt[id2].x)*(pt[iq1].y-pt[id2].y))
 			       ok=true;
			 }
		}
		if(!ok)
		   high=mid-1;
        else
           low=mid+1;
	} 
	rx=low%sg[id_layer+1].size();
	if(rx==u&&eq)
	{
		low=lm;
		high=rm;
	}
	else
	{
		low=sg[id_layer+1][rx].l;
	    high=sg[id_layer+1][rx].r;
	}
    while(low<=high)
	{
		int lq;
	    mid=(low+high)>>1;
		ie1=sg[id_layer+1][rx].id_layer;
		ip1=vec[ie1][mid];
		if(mid==sg[id_layer+1][rx].r)
		{
			ie2=sg[id_layer+1][(rx+1)%sg[id_layer+1].size()].id_layer;
			lq=sg[id_layer+1][(rx+1)%sg[id_layer+1].size()].l;
			ip2=vec[ie2][lq];
		}
		else
		    ip2=vec[ie1][mid+1];
		ok=false;
	    if(1LL*(pt[ip1].y-pt[id2].y)*(pt[ip2].x-pt[id2].x)<=1LL*(pt[ip1].x-pt[id2].x)*(pt[ip2].y-pt[id2].y))
	        ok=true;
		if(1LL*(pt[iq1].y-pt[id2].y)*(pt[iq2].x-pt[id2].x)>1LL*(pt[iq1].x-pt[id2].x)*(pt[iq2].y-pt[id2].y))
		{
			  if(ok)
			  {
  				 if(1LL*(pt[ip1].y-pt[id2].y)*(pt[iq1].x-pt[id2].x)<1LL*(pt[ip1].x-pt[id2].x)*(pt[iq1].y-pt[id2].y))
  				     ok=false;
  			  }
		}
	    else if(1LL*(pt[iq1].y-pt[id2].y)*(pt[iq2].x-pt[id2].x)<1LL*(pt[iq1].x-pt[id2].x)*(pt[iq2].y-pt[id2].y))
		{
			 if(!ok)
			 {
 			     if(1LL*(pt[ip1].y-pt[id2].y)*(pt[iq1].x-pt[id2].x)<=1LL*(pt[ip1].x-pt[id2].x)*(pt[iq1].y-pt[id2].y))
 			       ok=true;
			 }
		}
		if(!ok)
		   high=mid-1;
        else
           low=mid+1;
	}
	rr=low;
	if(gong_xian)
	{ 
		rx=cx;
		rr=cy;
	}
	else
	{
		if(eq)
		{
		  	if(1LL*(pt[iq1].y-pt[id2].y)*(pt[iq2].x-pt[id2].x)>1LL*(pt[iq1].x-pt[id2].x)*(pt[iq2].y-pt[id2].y))
		    { 
		    	rx=u;
		    	rr=rm;
		    }
		}
	}
    if(rr>sg[id_layer+1][rx].r)
    {
    	rx=(rx+1)%sg[id_layer+1].size();
    	rr=sg[id_layer+1][rx].l;
    }
   	now.id_layer=sg[id_layer+1][lx].id_layer;
    if(lx==rx&&ll<=rr)
    {
    	ie1=sg[id_layer+1][lx].id_layer;
	   	now.l=ll;
	   	now.r=rr;
	   	sg[id_layer].push_back(now);
	}
    else
    {
    	now.l=ll;
    	now.r=sg[id_layer+1][lx].r; 
    	sg[id_layer].push_back(now);
		for(i=(lx+1)%sg[id_layer+1].size();i!=rx;i=(i+1)%sg[id_layer+1].size())
    	{
    		now.id_layer=sg[id_layer+1][i].id_layer;
	    	now.l=sg[id_layer+1][i].l;
	    	now.r=sg[id_layer+1][i].r;
	    	sg[id_layer].push_back(now);
	    }
	    now.l=sg[id_layer+1][rx].l;
	    now.r=rr;
	    now.id_layer=sg[id_layer+1][rx].id_layer; 
	    sg[id_layer].push_back(now);
    }
}
int main()
{
   scanf("%d%d",&n,&m);
    int i,j,s,p,q,id,ip,ie,ll,rr,ip1,ip2;
    for(i=0;i<n;i++)
    { 
		scanf("%d%d",&pt[i].x,&pt[i].y);
        pt[i].id=i;
    }
    init();
    ans=-1;
    for(i=0;i<m;i++)
    {
      scanf("%d",&k);
        for(j=0;j<=k;j++)
            sg[j].clear();
        times++;
        int tr=ans%n;
        if(tr<0)
           tr+=n;
        int ma=0;
        for(j=0;j<k;j++)
        {
            scanf("%d",&list[j]);
            list[j]=(1LL*tr+1LL*list[j])%n;     
            vis[list[j]]=times;
        }
        times++;
        int nn=0;
        for(j=0;j<k;j++)
        {
            if(at[list[j]]>=0)
               list[nn++]=list[j];
        }
        k=nn;
        sort(list,list+k,cmp);
        nn=0;
        for(j=0;j<k;j++)
        {
        	if(nn==0||list[nn-1]!=list[j])
        	   list[nn++]=list[j];
		}
		k=nn;
        for(j=0;j<k;j++)
        {
        	if(j==0&&at[list[j]]!=0)
        	   break;
        	if(j&&at[list[j-1]]<at[list[j]]-1)
        	   break;
		}
		k=j;
		ma=-1;
        for(j=0;j<k;j++)
        {
            id=at[list[j]]; 
            if(ma<id)
                ma=id;
        }
        for(j=0;j<=ma+1;j++)
           sg[j].clear();
        j=ma+1;
        now.l=0;
        now.r=vec[j].size();
        now.id_layer=j;
        now.r--;
        if(now.l<=now.r)
           sg[j].push_back(now);
        ans=tot; 
        times++;
        for(j=k-1;j>=-1;j--)
        {
        	if(j<k-1&&(j<0||at[list[j]]!=at[list[j+1]]))
        	{
        		for(s=j+1;s<k;s++)
        		{
        			if(at[list[s]]!=at[list[j+1]])
        			   break;
				}
				id=at[list[j+1]];
				if(s-j-1==vec[id].size())
				{
					for(s=0;s<sg[id+1].size();s++)
						sg[id].push_back(sg[id+1][s]);
					continue;
				}
				q=vec[at[list[j+1]]].size()-1;
				for(p=s-1;p>j;p--)
				{
					if(as[list[p]]!=q)
					   break;
					q--;
				}
				p++; 
				int dx,dy;
				for(q=j+1;q<s;q++)
				{
					if(q==j+1)
					  dx=0;
					else
					  dx=as[list[q-1]]+1;
					if(as[list[q]]!=dx)
					{
					    if(dx!=0)
					    {
					       if(p==s)
					          dy=vec[id].size()-1;
					        else
					          dy=as[list[p]]-1;
						   got(id,vec[id][dy],vec[id][dx]);
					    }
						now.id_layer=id;
					    now.l=dx;
					    now.r=as[list[q]]-1;
					    sg[id].push_back(now);
					    p=q;
					}
				}
				if(as[list[s-1]]+1<vec[id].size())
				{
				    if(p==s)
					   dy=vec[id].size()-1;
			        else
			           dy=as[list[p]]-1;
				    dx=as[list[s-1]]+1;
				    got(id,vec[id][dy],vec[id][dx]);
					now.id_layer=id;
					now.l=as[list[s-1]]+1;
					now.r=vec[id].size()-1;
					sg[id].push_back(now);
				}
				else if(as[list[j+1]]!=0)
					got(id,vec[id][as[list[p]]-1],vec[id][0]);
			}
		}
		ans=0;
		for(int ii=0;ii<sg[0].size();ii++)
		{
			 id=sg[0][ii].id_layer;
			 ll=sg[0][ii].l;
			 rr=sg[0][ii].r;
			 ans+=sum[id][rr]-sum[id][ll];
			 ip1=vec[id][rr];
			 ie=sg[0][(ii+1)%sg[0].size()].id_layer;
			 ll=sg[0][(ii+1)%sg[0].size()].l;
			 ip2=vec[ie][ll];
			 ans+=1LL*(pt[ip2].y-my)*(pt[ip1].x-mx)-1LL*(pt[ip2].x-mx)*(pt[ip1].y-my);
		}
         printf("%lld\n",ans);
    }
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #197.26 us468 KBAcceptedScore: 5

Testcase #25.561 ms560 KBAcceptedScore: 5

Testcase #35.633 ms560 KBAcceptedScore: 5

Testcase #45.622 ms560 KBAcceptedScore: 5

Testcase #577.825 ms4 MB + 960 KBAcceptedScore: 5

Testcase #682.518 ms5 MB + 348 KBAcceptedScore: 5

Testcase #782.613 ms5 MB + 348 KBAcceptedScore: 5

Testcase #886.425 ms5 MB + 756 KBAcceptedScore: 5

Testcase #9104.96 ms4 MB + 652 KBAcceptedScore: 5

Testcase #10111.451 ms5 MB + 28 KBAcceptedScore: 5

Testcase #11117.006 ms4 MB + 664 KBAcceptedScore: 5

Testcase #12168.209 ms4 MB + 800 KBAcceptedScore: 5

Testcase #13501.638 ms4 MB + 472 KBAcceptedScore: 5

Testcase #14566.511 ms4 MB + 620 KBAcceptedScore: 5

Testcase #15981.743 ms6 MB + 52 KBAcceptedScore: 5

Testcase #16951.796 ms5 MB + 344 KBAcceptedScore: 5

Testcase #171.008 s5 MB + 524 KBAcceptedScore: 5

Testcase #181.016 s5 MB + 712 KBAcceptedScore: 5

Testcase #191.084 s5 MB + 896 KBAcceptedScore: 5

Testcase #201.111 s6 MB + 56 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-11-25 10:58:40 | Loaded in 2 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠