oj.uz

Submission #202119

# Submission time Handle Problem Language Result Execution time Memory
202119 2020-02-14T00:42:53 Z Segtree Golf (JOI17_golf) C++14
10 / 100
 1703 ms 138232 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 2020
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 5 ms 512 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 105 ms 4864 KB Output is correct
5 Correct 1174 ms 50624 KB Output is correct
6 Correct 1227 ms 53728 KB Output is correct
7 Correct 1307 ms 49884 KB Output is correct
8 Correct 1014 ms 55152 KB Output is correct
9 Correct 1531 ms 51472 KB Output is correct
10 Correct 1353 ms 54328 KB Output is correct
11 Correct 1090 ms 56312 KB Output is correct
12 Correct 1039 ms 52668 KB Output is correct
13 Correct 1217 ms 53752 KB Output is correct
14 Correct 1703 ms 54724 KB Output is correct
15 Correct 174 ms 16120 KB Output is correct
16 Correct 858 ms 51868 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 5 ms 512 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 105 ms 4864 KB Output is correct
5 Correct 1174 ms 50624 KB Output is correct
6 Correct 1227 ms 53728 KB Output is correct
7 Correct 1307 ms 49884 KB Output is correct
8 Correct 1014 ms 55152 KB Output is correct
9 Correct 1531 ms 51472 KB Output is correct
10 Correct 1353 ms 54328 KB Output is correct
11 Correct 1090 ms 56312 KB Output is correct
12 Correct 1039 ms 52668 KB Output is correct
13 Correct 1217 ms 53752 KB Output is correct
14 Correct 1703 ms 54724 KB Output is correct
15 Correct 174 ms 16120 KB Output is correct
16 Correct 858 ms 51868 KB Output is correct
17 Runtime error 147 ms 138232 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 5 ms 512 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 105 ms 4864 KB Output is correct
5 Correct 1174 ms 50624 KB Output is correct
6 Correct 1227 ms 53728 KB Output is correct
7 Correct 1307 ms 49884 KB Output is correct
8 Correct 1014 ms 55152 KB Output is correct
9 Correct 1531 ms 51472 KB Output is correct
10 Correct 1353 ms 54328 KB Output is correct
11 Correct 1090 ms 56312 KB Output is correct
12 Correct 1039 ms 52668 KB Output is correct
13 Correct 1217 ms 53752 KB Output is correct
14 Correct 1703 ms 54724 KB Output is correct
15 Correct 174 ms 16120 KB Output is correct
16 Correct 858 ms 51868 KB Output is correct
17 Runtime error 147 ms 138232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -