Submission #1214746

---

Source Code Expand

#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=70000+1;
const int DX[]={-1,0,+1,0},DY[]={0,+1,0,-1}; char DC[]={'N','E','S','W'};
typedef struct P { int u,v,idx,t; } P;
bool operator<(const P &a,const P &b) { if(a.t!=b.t) return a.t<b.t; if(a.u!=b.u) return a.u<b.u; if(a.v!=b.v) return a.v<b.v; return a.idx<b.idx; }

int h,w,n,dcost;
int sx,sy,tx,ty;

int ax[MAXN],ay[MAXN],ak[MAXN],ad[MAXN],akcost[MAXN];
ll d[MAXN];


P p[2*MAXN];
ll mninc[8*MAXN],mndec[8*MAXN],mn[8*MAXN]; int fst[8*MAXN],lst[8*MAXN],mnpos[8*MAXN];

void updinc(int x,ll val) {
	if(val>=mninc[x]) return;
	mninc[x]=val; if(fst[x]!=-1) { ll cur=mninc[x]+(ll)dcost*p[fst[x]].v; if(cur<mn[x]) mn[x]=cur,mnpos[x]=fst[x]; }
}
void upddec(int x,ll val) {
	if(val>=mndec[x]) return;
	mndec[x]=val; if(lst[x]!=-1) { ll cur=mndec[x]-(ll)dcost*p[lst[x]].v; if(cur<mn[x]) mn[x]=cur,mnpos[x]=lst[x]; }
}
void spush(int x) {
	if(mninc[x]!=LLONG_MAX) updinc(2*x+1,mninc[x]),updinc(2*x+2,mninc[x]),mninc[x]=LLONG_MAX;
	if(mndec[x]!=LLONG_MAX) upddec(2*x+1,mndec[x]),upddec(2*x+2,mndec[x]),mndec[x]=LLONG_MAX;
}
void scalc(int x) {
	fst[x]=fst[2*x+1]!=-1?fst[2*x+1]:fst[2*x+2];
	lst[x]=lst[2*x+2]!=-1?lst[2*x+2]:lst[2*x+1];
	mn[x]=LLONG_MAX,mnpos[x]=-1;
	if(mninc[x]!=LLONG_MAX&&fst[x]!=-1) { ll cur=mninc[x]+(ll)dcost*p[fst[x]].v; if(cur<mn[x]) mn[x]=cur,mnpos[x]=fst[x]; }
	if(mndec[x]!=LLONG_MAX&&lst[x]!=-1) { ll cur=mndec[x]-(ll)dcost*p[lst[x]].v; if(cur<mn[x]) mn[x]=cur,mnpos[x]=lst[x]; }
	if(mn[2*x+1]<mn[x]) mn[x]=mn[2*x+1],mnpos[x]=mnpos[2*x+1];
	if(mn[2*x+2]<mn[x]) mn[x]=mn[2*x+2],mnpos[x]=mnpos[2*x+2];
}
void sinit(int x,int l,int r) {
	mninc[x]=mndec[x]=LLONG_MAX;
	if(l==r) { mn[x]=LLONG_MAX; fst[x]=lst[x]=mnpos[x]=l; return; }
	int m=l+(r-l)/2;
	sinit(2*x+1,l,m); sinit(2*x+2,m+1,r);
	scalc(x);
}
void sset(int x,int l,int r,int POS,ll VAL) {
	if(l==r) { mn[x]=VAL; return; }
	int m=l+(r-l)/2;
	spush(x);
	if(POS<=m) sset(2*x+1,l,m,POS,VAL); else sset(2*x+2,m+1,r,POS,VAL);
	scalc(x);
}
void skill(int x,int l,int r,int POS) {
	if(l==r) { fst[x]=lst[x]=mnpos[x]=-1; mn[x]=LLONG_MAX; return; }
	int m=l+(r-l)/2;
	spush(x);
	if(POS<=m) skill(2*x+1,l,m,POS); else skill(2*x+2,m+1,r,POS);
	scalc(x);
}
void sinc(int x,int l,int r,int T,int U,int V,ll VAL) {
	if(T<p[l].t||T==p[l].t&&(U<p[l].u)) return;
	if(T>p[r].t||T==p[r].t&&(U>p[r].u||U==p[r].u&&(V>p[r].v))) return;
	//printf("sinc(%d,%d..%d,[%d,%d,%d],%lld) [%d,%d,%d] [%d,%d,%d]\n",x,l,r,T,U,V,VAL,p[l].t,p[l].u,p[l].v,p[r].t,p[r].u,p[r].v);
	if(T==p[l].t&&T==p[r].t&&U==p[l].u&&U==p[r].u&&V<=p[l].v) {
		updinc(x,VAL);
	} else {
		int m=l+(r-l)/2;
		spush(x);
		sinc(2*x+1,l,m,T,U,V,VAL);
		sinc(2*x+2,m+1,r,T,U,V,VAL);
		scalc(x);
	}
}
void sdec(int x,int l,int r,int T,int U,int V,ll VAL) {
	if(T<p[l].t||T==p[l].t&&(U<p[l].u||U==p[l].u&&(V<p[l].v))) return;
	if(T>p[r].t||T==p[r].t&&(U>p[r].u)) return;
	if(T==p[l].t&&T==p[r].t&&U==p[l].u&&U==p[r].u&&V>=p[r].v) {
		upddec(x,VAL);
	} else {
		int m=l+(r-l)/2;
		spush(x);
		sdec(2*x+1,l,m,T,U,V,VAL);
		sdec(2*x+2,m+1,r,T,U,V,VAL);
		scalc(x);
	}
}

ll solve() {
	ax[n]=tx,ay[n]=ty,ak[n]=-1,ad[n]=0,akcost[n]=0,++n;

	REP(i,n) p[i].u=ax[i],p[i].v=ay[i],p[i].idx=i,p[i].t=0;
	REP(i,n) p[n+i].u=ay[i],p[n+i].v=ax[i],p[n+i].idx=i,p[n+i].t=1;
	sort(p,p+2*n);
	sinit(0,0,2*n-1);
	REP(i,n) d[i]=LLONG_MAX;
	REP(i,2*n) if(p[i].t==0&&p[i].u==sx&&p[i].v==sy||p[i].t==1&&p[i].u==sy&&p[i].v==sx) sset(0,0,2*n-1,i,0);
	while(mn[0]!=LLONG_MAX) {
		int pos=mnpos[0],idx=p[pos].idx; ll cost=mn[0];
		//printf("pos=%d (u=%d,v=%d,idx=%d,t=%d) = %lld\n",pos,p[pos].u,p[pos].v,p[pos].idx,p[pos].t,cost);
		skill(0,0,2*n-1,pos);
		if(d[idx]==LLONG_MAX) d[idx]=cost; else { assert(cost>=d[idx]); continue; }
		if(ak[idx]==-1) continue;
		REP(k,4) {
			ll ncost=cost+(k==ak[idx]?0:akcost[idx]);
			int x=ax[idx]+ad[idx]*DX[k],y=ay[idx]+ad[idx]*DY[k],t=DX[k]==0?0:1,u=t==0?x:y,v=t==0?y:x;
			//printf("\t->(%d,%d)=%lld (%d,%d)\n",x,y,ncost,DX[k],DY[k]);
			sdec(0,0,2*n-1,t,u,v,ncost+(ll)dcost*v);
			sinc(0,0,2*n-1,t,u,v,ncost-(ll)dcost*v);
		}
	}
	ll ret=d[n-1];
	return ret==LLONG_MAX?-1:ret;
}


void run() {
	scanf("%d%d%d%d",&h,&w,&n,&dcost);
	scanf("%d%d%d%d",&sx,&sy,&tx,&ty); --sx,--sy,--tx,--ty;
	REP(i,n) { char c; scanf("%d%d %c%d%d",&ax[i],&ay[i],&c,&ad[i],&akcost[i]); --ax[i],--ay[i],ak[i]=-1; REP(k,4) if(DC[k]==c) ak[i]=k; assert(ak[i]!=-1); }
	ll ret=solve();
	printf("%lld\n",ret);
}

void stress() {
	while(true) {
		n=MAXN-1; REP(i,n) ax[i]=rand()%1000,ay[i]=rand()%1000,ak[i]=rand()%4,ad[i]=rand()%1000,akcost[i]=rand()%1000;
		dcost=rand()%1000; { int s=rand()%n; sx=ax[s],sy=ay[s]; } tx=rand()%1000,ty=rand()%1000;
		//printf("? ? %d %d\n",n,dcost); printf("%d %d %d %d\n",sx+1,sy+1,tx+1,ty+1); REP(i,n) printf("%d %d %c %d %d\n",ax[i]+1,ay[i]+1,DC[ak[i]],ad[i],akcost[i]);
		solve(); puts(".");
	}
}

int main() {
	//stress();
	run();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void run()’:
./Main.cpp:147:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&h,&w,&n,&dcost);
                                   ^
./Main.cpp:148:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&sx,&sy,&tx,&ty); --sx,--sy,--tx,--ty;
                                   ^
./Main.cpp:149:76: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  REP(i,n) { char c; scanf("%d%d %c%d%d",&ax[i],&ay[i],&c,&ad[i],&akcost[i]); --ax[i],--ay[i],ak[i]=-1; REP(k,4) if(DC[k]==c) ak[i]=k; assert(ak[i]!=-1); }
                                                                            ^

Judge Result