Submission #14736

#	Time	Username	Problem	Language	Result	Execution time	Memory
14736		gs13068	Palembang Bridges (APIO15_bridge)	C++98	63 / 100	2000 ms	20220 KiB

bridge

#include<cstdio>
#include<algorithm>

int p[111111];
int s[111111];
int q[111111];
int t[111111];
char pp[11],qq[11];
int x[222222];
std::pair<int,int> d[111111];
int dn;

long long L[111111];
long long R[111111];

struct tree
{
	int l;
	int r;
    int s;
    int e;
    int t;
    long long x;
} T[444444];
int Tn;
int stat=-1;
long long now;

int n;

void init(int i,int s,int e)
{
    T[i].s = s;
    T[i].e = e;
    if(e-s>1)
    {
		T[i].l=Tn++;
		T[i].r=Tn++;
        init(T[i].l,s,(s+e)/2);
        init(T[i].r,(s+e)/2,e);
    }
}

void add(int i,int s,int e,int t)
{
	if(s<T[i].s)s=T[i].s;
	if(e>T[i].e)e=T[i].e;
	if(s>=e)return;
	if(t>0)T[i].x+=x[e]-x[s];
	else T[i].x-=x[e]-x[s];
	if(s==T[i].s&&e==T[i].e)
	{
		T[i].t+=t;
		return;
	}
	add(T[i].l,s,e,t);
	add(T[i].r,s,e,t);
}

long long get(int i,int s,int e)
{
	if(s<T[i].s)s=T[i].s;
	if(e>T[i].e)e=T[i].e;
	if(s>=e)return 0LL;
    if(s==T[i].s&&e==T[i].e)return T[i].x;
    return 1LL*(x[e]-x[s])*T[i].t+get(T[i].l,s,e)+get(T[i].r,s,e);
}

int get_t(int i,int t)
{
	if(t<T[i].s||t>=T[i].e)return 0;
    if(t==T[i].s&&t+1==T[i].e)return T[i].t;
    return T[i].t+get_t(T[i].l,t)+get_t(T[i].r,t);
}

void calcL(int ss,int ee,int l,int r)
{
	if(ss>=ee)return;
	long long tt;
    int i,j,m=(ss+ee)/2;
    int ll,rr;
    while(stat<m)
    {
		++stat;
		j=d[stat].second;
		now+=x[std::min(s[j],t[j])]-x[0];
		add(0,0,std::min(s[j],t[j]),-1);
		add(0,std::max(s[j],t[j]),n+n-1,1);
    }
    while(stat>m)
    {
		j=d[stat].second;
		now-=x[std::min(s[j],t[j])]-x[0];
		add(0,0,std::min(s[j],t[j]),1);
		add(0,std::max(s[j],t[j]),n+n-1,-1);
		stat--;
    }

    ll=rr=l;
    tt=L[m]=now+get(0,0,l);
    for(i=l+1;i<r;i++)
    {
		tt+=1LL*(x[i]-x[i-1])*get_t(0,i-1);
		if(L[m]>tt)
		{
			L[m]=tt;
            ll=rr=i;
		}
        if(L[m]==tt)rr=i;
	}

	i=std::upper_bound(x,x+n+n-1,(x[ll]+x[rr]+1)/2)-x;

	calcL(ss,m,l,i);
	calcL(m+1,ee,i-1,r);
}

void calcR(int ss,int ee,int l,int r)
{
	if(ss>=ee)return;
	long long tt;
    int i,j,m=(ss+ee)/2;
    int ll,rr;
    while(stat>m)
    {
		--stat;
		j=d[stat].second;
		now+=x[std::min(s[j],t[j])]-x[0];
		add(0,0,std::min(s[j],t[j]),-1);
		add(0,std::max(s[j],t[j]),n+n-1,1);
    }
    while(stat<m)
    {
		j=d[stat].second;
		now-=x[std::min(s[j],t[j])]-x[0];
		add(0,0,std::min(s[j],t[j]),1);
		add(0,std::max(s[j],t[j]),n+n-1,-1);
		stat++;
    }

    ll=rr=l;
    tt=R[m]=now+get(0,0,l);
    for(i=l+1;i<r;i++)
    {
		tt+=1LL*(x[i]-x[i-1])*get_t(0,i-1);
		if(R[m]>tt)
		{
			R[m]=tt;
            ll=rr=i;
		}
        if(R[m]==tt)rr=i;
	}

	i=std::upper_bound(x,x+n+n-1,(x[ll]+x[rr]+1)/2)-x;

	calcR(ss,m,l,i);
	calcR(m+1,ee,i-1,r);
}

int main()
{
	//freopen("input","r",stdin);
	//freopen("output","w",stdout);
	long long res=0;
	int i,j,m,ss,ee,l,r;
	int fir,sec;
	long long min;
	scanf("%d%d",&m,&n);
	if(m==1)
	{
		j=0;
        for(i=0;i<n;i++)
        {
			scanf("%s%d%s%d",pp,&s[i],qq,&t[i]);
			p[i]=pp[0]-'A';
			q[i]=qq[0]-'A';
			if(p[i]!=q[i])
			{
				j++;
				d[dn++]=std::make_pair(std::min(s[i],t[i]),-1);
				d[dn++]=std::make_pair(std::max(s[i],t[i]),-1);
			}
        }
        std::sort(d,d+dn);
        for(i=0;i<dn;i++)
        {
			j+=d[i].second;
            if(j<=0)break;
        }
        for(j=0;j<n;j++)
        {
			if(p[j]!=q[j])res+=std::abs(s[j]-d[i].first)+std::abs(t[j]-d[i].first)+1;
			else res+=std::abs(s[j]-t[j]);
        }
        printf("%lld\n",res);
		return 0;
	}

	for(i=0;i<n;i++)
	{
		scanf("%s%d%s%d",pp,&s[i],qq,&t[i]);
		p[i]=pp[0]-'A';
		q[i]=qq[0]-'A';
		//s[i]=2*i;
		//t[i]=2*i+1;
		x[i]=s[i];
		x[i+n]=t[i];
	}

    for(i=0;i<n;i++)if(p[i]!=q[i])d[dn++]=std::make_pair(s[i]+t[i],i);

	std::sort(x,x+n+n);
	for(i=0;i<n;i++)
	{
		s[i]=std::lower_bound(x,x+n+n,s[i])-x;
		t[i]=std::lower_bound(x,x+n+n,t[i])-x;
	}

	if(dn)
	{
		std::sort(d,d+dn);

		Tn=1;
		init(0,0,n+n-1);

		calcL(0,dn,0,n+n-1);

		for(i=0;i<Tn;i++)T[i].x=T[i].t=0;

		now=0;
		stat=dn;

		calcR(0,dn,0,n+n-1);

		res=std::min(L[dn-1],R[0]);
		for(i=1;i<dn;i++)res=std::min(res,L[i-1]+R[i]);
	}
	else res=0;

	res*=2;

	for(i=0;i<n;i++)
	{
		res+=std::abs(x[s[i]]-x[t[i]]);
		res+=p[i]!=q[i];
	}

	printf("%lld\n",res);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:165:12: warning: unused variable 'ss' [-Wunused-variable]
  int i,j,m,ss,ee,l,r;
            ^
bridge.cpp:165:15: warning: unused variable 'ee' [-Wunused-variable]
  int i,j,m,ss,ee,l,r;
               ^
bridge.cpp:165:18: warning: unused variable 'l' [-Wunused-variable]
  int i,j,m,ss,ee,l,r;
                  ^
bridge.cpp:165:20: warning: unused variable 'r' [-Wunused-variable]
  int i,j,m,ss,ee,l,r;
                    ^
bridge.cpp:166:6: warning: unused variable 'fir' [-Wunused-variable]
  int fir,sec;
      ^
bridge.cpp:166:10: warning: unused variable 'sec' [-Wunused-variable]
  int fir,sec;
          ^
bridge.cpp:167:12: warning: unused variable 'min' [-Wunused-variable]
  long long min;
            ^
bridge.cpp:168:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&m,&n);
                     ^
bridge.cpp:174:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s%d%s%d",pp,&s[i],qq,&t[i]);
                                       ^
bridge.cpp:201:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%s%d",pp,&s[i],qq,&t[i]);
                                      ^

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37