Submission #202117

#	Time	Username	Problem	Language	Result	Execution time	Memory
202117		Segtree	Golf (JOI17_golf)	C++14	10 / 100	1683 ms	136824 KiB

golf

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define pb push_back
#define lo(x,y) (lower_bound(all(x),y)-x.begin())*2
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 2010
ll n,s,t,u,v,a[N],b[N],c[N],d[N];
bool av[N][N];
ll dist[N][N][2];
struct qry{
    ll x,y,dir,cost;
};
queue<qry> Q;
int main(){
    cin>>s>>t>>u>>v>>n;
    vector<ll> xs,ys;
    xs.pb(-2e9); ys.pb(-2e9);
    xs.pb(2e9); ys.pb(2e9);
    xs.pb(s); ys.pb(t);
    xs.pb(u); ys.pb(v);
    rep(i,n){
	cin>>a[i]>>b[i]>>c[i]>>d[i];
	xs.pb(a[i]); xs.pb(b[i]);
	ys.pb(c[i]); ys.pb(d[i]);
    }
    sort(all(xs)); sort(all(ys));
    xs.erase(unique(all(xs)),xs.end());
    ys.erase(unique(all(ys)),ys.end());
    s=lo(xs,s),t=lo(ys,t);
    u=lo(xs,u),v=lo(ys,v);
    rep(i,n){
	a[i]=lo(xs,a[i]); b[i]=lo(xs,b[i]);
	c[i]=lo(ys,c[i]); d[i]=lo(ys,d[i]);
    }
    ll h=xs.size()*2,w=ys.size()*2;
    //cout<<"h"; rep(i,h)cout<<xs[i]<<" "; cout<<endl;
    //cout<<s<<" "<<t<<" "<<u<<" "<<v<<endl;
    //rep(i,n)cout<<a[i]<<" "<<b[i]<<" "<<c[i]<<" "<<d[i]<<endl;
    rep(i,h)rep(j,w){
	av[i][j]=1;
	rep(k,2)dist[i][j][k]=1e17;
    }
    rep(i,n){
	for(int x=a[i]+1;x<b[i];x++)for(int y=c[i]+1;y<d[i];y++){
	    av[x][y]=0;
	}
    }
    /*rep(i,h){
	rep(j,w)cout<<av[i][j];
	cout<<endl;
    }*/
    Q.push((struct qry){s,t,0,1});
    Q.push((struct qry){s,t,1,1});
    while(!Q.empty()){
	struct qry e=Q.front(); Q.pop();
	if(not(0<=e.x&&e.x<h&&0<=e.y&&e.y<w))continue;
	if(av[e.x][e.y]==0)continue;
	if(dist[e.x][e.y][e.dir]<=e.cost)continue;
	dist[e.x][e.y][e.dir]=e.cost;
	ll dx[]={0,1,0,-1},dy[]={1,0,-1,0};
	rep(r,4){
	    Q.push((struct qry){e.x+dx[r],e.y+dy[r],r%2,e.cost+(r%2!=e.dir)});
	}
    }
    cout<<min(dist[u][v][0],dist[u][v][1])<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70