oj.uz

Submission #202117

# Submission time Handle Problem Language Result Execution time Memory
202117 2020-02-14T00:42:02 Z Segtree Golf (JOI17_golf) C++14
10 / 100
 1683 ms 136824 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 49 ms 4864 KB Output is correct
5 Correct 1194 ms 50536 KB Output is correct
6 Correct 1276 ms 53788 KB Output is correct
7 Correct 1361 ms 49900 KB Output is correct
8 Correct 1080 ms 55404 KB Output is correct
9 Correct 1386 ms 51296 KB Output is correct
10 Correct 1444 ms 54392 KB Output is correct
11 Correct 1081 ms 56312 KB Output is correct
12 Correct 1222 ms 53000 KB Output is correct
13 Correct 1363 ms 53752 KB Output is correct
14 Correct 1683 ms 54988 KB Output is correct
15 Correct 182 ms 16120 KB Output is correct
16 Correct 829 ms 51876 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 49 ms 4864 KB Output is correct
5 Correct 1194 ms 50536 KB Output is correct
6 Correct 1276 ms 53788 KB Output is correct
7 Correct 1361 ms 49900 KB Output is correct
8 Correct 1080 ms 55404 KB Output is correct
9 Correct 1386 ms 51296 KB Output is correct
10 Correct 1444 ms 54392 KB Output is correct
11 Correct 1081 ms 56312 KB Output is correct
12 Correct 1222 ms 53000 KB Output is correct
13 Correct 1363 ms 53752 KB Output is correct
14 Correct 1683 ms 54988 KB Output is correct
15 Correct 182 ms 16120 KB Output is correct
16 Correct 829 ms 51876 KB Output is correct
17 Runtime error 145 ms 136824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 49 ms 4864 KB Output is correct
5 Correct 1194 ms 50536 KB Output is correct
6 Correct 1276 ms 53788 KB Output is correct
7 Correct 1361 ms 49900 KB Output is correct
8 Correct 1080 ms 55404 KB Output is correct
9 Correct 1386 ms 51296 KB Output is correct
10 Correct 1444 ms 54392 KB Output is correct
11 Correct 1081 ms 56312 KB Output is correct
12 Correct 1222 ms 53000 KB Output is correct
13 Correct 1363 ms 53752 KB Output is correct
14 Correct 1683 ms 54988 KB Output is correct
15 Correct 182 ms 16120 KB Output is correct
16 Correct 829 ms 51876 KB Output is correct
17 Runtime error 145 ms 136824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -