oj.uz

Submission #202120

# Submission time Handle Problem Language Result Execution time Memory
202120 2020-02-14T00:43:44 Z Segtree Golf (JOI17_golf) C++14
10 / 100
 10000 ms 269592 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 4020
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 640 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 51 ms 5632 KB Output is correct
5 Correct 1215 ms 53496 KB Output is correct
6 Correct 1481 ms 57020 KB Output is correct
7 Correct 1535 ms 53256 KB Output is correct
8 Correct 1544 ms 58652 KB Output is correct
9 Correct 1520 ms 54416 KB Output is correct
10 Correct 1417 ms 57680 KB Output is correct
11 Correct 1285 ms 59648 KB Output is correct
12 Correct 1108 ms 56080 KB Output is correct
13 Correct 1235 ms 56960 KB Output is correct
14 Correct 1734 ms 58024 KB Output is correct
15 Correct 191 ms 17656 KB Output is correct
16 Correct 1139 ms 55064 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 640 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 51 ms 5632 KB Output is correct
5 Correct 1215 ms 53496 KB Output is correct
6 Correct 1481 ms 57020 KB Output is correct
7 Correct 1535 ms 53256 KB Output is correct
8 Correct 1544 ms 58652 KB Output is correct
9 Correct 1520 ms 54416 KB Output is correct
10 Correct 1417 ms 57680 KB Output is correct
11 Correct 1285 ms 59648 KB Output is correct
12 Correct 1108 ms 56080 KB Output is correct
13 Correct 1235 ms 56960 KB Output is correct
14 Correct 1734 ms 58024 KB Output is correct
15 Correct 191 ms 17656 KB Output is correct
16 Correct 1139 ms 55064 KB Output is correct
17 Execution timed out 10123 ms 269592 KB Time limit exceeded
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 640 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 51 ms 5632 KB Output is correct
5 Correct 1215 ms 53496 KB Output is correct
6 Correct 1481 ms 57020 KB Output is correct
7 Correct 1535 ms 53256 KB Output is correct
8 Correct 1544 ms 58652 KB Output is correct
9 Correct 1520 ms 54416 KB Output is correct
10 Correct 1417 ms 57680 KB Output is correct
11 Correct 1285 ms 59648 KB Output is correct
12 Correct 1108 ms 56080 KB Output is correct
13 Correct 1235 ms 56960 KB Output is correct
14 Correct 1734 ms 58024 KB Output is correct
15 Correct 191 ms 17656 KB Output is correct
16 Correct 1139 ms 55064 KB Output is correct
17 Execution timed out 10123 ms 269592 KB Time limit exceeded
18 Halted 0 ms 0 KB -