Submission #67562418

---

Source Code Expand

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define M 998244353
using namespace std;
struct nde{
	int l,r,dy;
} gip[400010],gin[400010],gop[400010],gon[400010];
int hea[10000000],nex[10000000],to[10000000];
ll wei[10000000];
ll dis[10000000];
int inq[10000000];
ll lc[10000000];
ll lf,rf,lt,rt,c;
deque<int> q;
int n,m;
int pc;
int p;
void ae(int x,int y,ll w){
	nex[++p]=hea[x];
	hea[x]=p;
	to[p]=y;
	wei[p]=w;
}
void btip(int p,int l,int r){
	gip[p].l=l;
	gip[p].r=r;
	gip[p].dy=++pc;
	if(l==r) ae(gip[p].dy,l,lc[l]);
	else{
		btip(p*2,l,(l+r)/2);
		btip(p*2+1,(l+r)/2+1,r);
		ae(gip[p].dy,gip[p*2].dy,0);
		ae(gip[p].dy,gip[p*2+1].dy,0);
	}
}
void btin(int p,int l,int r){
	gin[p].l=l;
	gin[p].r=r;
	gin[p].dy=++pc;
	if(l==r) ae(gin[p].dy,l,-lc[l]);
	else{
		btin(p*2,l,(l+r)/2);
		btin(p*2+1,(l+r)/2+1,r);
		ae(gin[p].dy,gin[p*2].dy,0);
		ae(gin[p].dy,gin[p*2+1].dy,0);
	}
}
void btop(int p,int l,int r){
	gop[p].l=l;
	gop[p].r=r;
	gop[p].dy=++pc;
	if(l==r) ae(l,gop[p].dy,lc[l]);
	else{
		btop(p*2,l,(l+r)/2);
		btop(p*2+1,(l+r)/2+1,r);
		ae(gop[p*2].dy,gop[p].dy,0);
		ae(gop[p*2+1].dy,gop[p].dy,0);
	}
}
void bton(int p,int l,int r){
	gon[p].l=l;
	gon[p].r=r;
	gon[p].dy=++pc;
	if(l==r) ae(l,gon[p].dy,-lc[l]);
	else{
		bton(p*2,l,(l+r)/2);
		bton(p*2+1,(l+r)/2+1,r);
		ae(gon[p*2].dy,gon[p].dy,0);
		ae(gon[p*2+1].dy,gon[p].dy,0);
	}
}
void aet(nde g[],int p,int l,int r,int ot,int to,ll w){
	l=max(l,g[p].l);
	r=min(r,g[p].r);
	if(l>r) return ;
	if(l==g[p].l&&r==g[p].r){
		if(ot==1) ae(g[p].dy,to,w);
		else ae(to,g[p].dy,w);
		return ;
	}
	aet(g,p*2,l,r,ot,to,w);
	aet(g,p*2+1,l,r,ot,to,w);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&lc[i]);
	pc=n;
	btip(1,1,n);
	btin(1,1,n);
	btop(1,1,n);
	bton(1,1,n);
	while(m--){
		scanf("%d%d%d%d%lld",&lf,&rf,&lt,&rt,&c);
		pc++;
		if(rf<=lt){
			aet(gon,1,lf,rf,1,pc,0);
			aet(gip,1,lt,rt,0,pc,c);
		}
		else{
			aet(gop,1,lf,rf,1,pc,0);
			aet(gin,1,lt,rt,0,pc,c);
		}
	}
	ll inf=5e18;
	for(int i=2;i<=pc;i++) dis[i]=inf;
	inq[1]=1;
	q.push_front(1);
	while(!q.empty()){
		int tmp=q.front(),tmp2=q.back();
		q.pop_front();
		if(!q.empty()){
			q.pop_back();
			if(dis[tmp]>dis[tmp2]) swap(tmp,tmp2);
			q.push_back(tmp2);
		}
		inq[tmp]=0;
		for(int i=hea[tmp];i!=0;i=nex[i]){
			if(dis[to[i]]>dis[tmp]+wei[i]){
				dis[to[i]]=dis[tmp]+wei[i];
				if(inq[to[i]]==0){
					inq[to[i]]=1;
					if(!q.empty()){
						if(dis[to[i]]<dis[q.front()]) q.push_front(to[i]);
						else q.push_back(to[i]);
					}
					else q.push_back(to[i]);
				}
			}
		}
	}
	for(int i=2;i<=n;i++){
		if(dis[i]<inf) printf("%lld ",dis[i]);
		else printf("-1 ");
	}
	printf("\n");
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:94:25: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
   94 |                 scanf("%d%d%d%d%lld",&lf,&rf,&lt,&rt,&c);
      |                        ~^            ~~~
      |                         |            |
      |                         int*         long long int*
      |                        %lld
Main.cpp:94:27: warning: format ‘%d’ expects argument of type ‘int*’, but argument 3 has type ‘long long int*’ [-Wformat=]
   94 |                 scanf("%d%d%d%d%lld",&lf,&rf,&lt,&rt,&c);
      |                          ~^              ~~~
      |                           |              |
      |                           int*           long long int*
      |                          %lld
Main.cpp:94:29: warning: format ‘%d’ expects argument of type ‘int*’, but argument 4 has type ‘long long int*’ [-Wformat=]
   94 |                 scanf("%d%d%d%d%lld",&lf,&rf,&lt,&rt,&c);
      |                            ~^                ~~~
      |                             |                |
      |                             int*             long long int*
      |                            %lld
Main.cpp:94:31: warning: format ‘%d’ expects argument of type ‘int*’, but argument 5 has type ‘long long int*’ [-Wformat=]
   94 |                 scanf("%d%d%d%d%lld",&lf,&rf,&lt,&rt,&c);
      |                              ~^                  ~~~
      |                               |                  |
      |                               int*               long long int*
      |                              %lld
Main.cpp:86:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:87:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |         for(int i=1;i<=n;i++) scanf("%lld",&lc[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~
Main.cpp:94:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   94 |                 scanf("%d%d%d%d%lld",&lf,&rf,&lt,&rt,&c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result