oj.uz

Submission #202121

# Submission time Handle Problem Language Result Execution time Memory
202121 2020-02-14T00:47:43 Z Segtree Golf (JOI17_golf) C++14
30 / 100
 4304 ms 271776 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){
	    ll xx=e.x+dx[r],yy=e.y+dy[r];
	    if(0<=xx&&xx<h&&0<=yy&&yy<w&&av[xx][yy]){
		Q.push((struct qry){e.x+dx[r]*2,e.y+dy[r]*2,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 20 ms 5504 KB Output is correct
5 Correct 453 ms 52576 KB Output is correct
6 Correct 384 ms 56056 KB Output is correct
7 Correct 393 ms 52192 KB Output is correct
8 Correct 316 ms 57720 KB Output is correct
9 Correct 426 ms 53740 KB Output is correct
10 Correct 528 ms 56708 KB Output is correct
11 Correct 366 ms 59180 KB Output is correct
12 Correct 349 ms 55544 KB Output is correct
13 Correct 398 ms 56192 KB Output is correct
14 Correct 467 ms 57240 KB Output is correct
15 Correct 65 ms 17400 KB Output is correct
16 Correct 266 ms 54364 KB Output is correct

Subtask #2
20.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 20 ms 5504 KB Output is correct
5 Correct 453 ms 52576 KB Output is correct
6 Correct 384 ms 56056 KB Output is correct
7 Correct 393 ms 52192 KB Output is correct
8 Correct 316 ms 57720 KB Output is correct
9 Correct 426 ms 53740 KB Output is correct
10 Correct 528 ms 56708 KB Output is correct
11 Correct 366 ms 59180 KB Output is correct
12 Correct 349 ms 55544 KB Output is correct
13 Correct 398 ms 56192 KB Output is correct
14 Correct 467 ms 57240 KB Output is correct
15 Correct 65 ms 17400 KB Output is correct
16 Correct 266 ms 54364 KB Output is correct
17 Correct 3462 ms 266356 KB Output is correct
18 Correct 3029 ms 265344 KB Output is correct
19 Correct 2386 ms 268032 KB Output is correct
20 Correct 3233 ms 269144 KB Output is correct
21 Correct 4304 ms 271776 KB Output is correct
22 Correct 3003 ms 270868 KB Output is correct
23 Correct 2971 ms 270940 KB Output is correct
24 Correct 2551 ms 271144 KB Output is correct
25 Correct 1778 ms 270060 KB Output is correct
26 Correct 2436 ms 270460 KB Output is correct
27 Correct 93 ms 23160 KB Output is correct
28 Correct 300 ms 64120 KB Output is correct
29 Correct 316 ms 65656 KB Output is correct

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 20 ms 5504 KB Output is correct
5 Correct 453 ms 52576 KB Output is correct
6 Correct 384 ms 56056 KB Output is correct
7 Correct 393 ms 52192 KB Output is correct
8 Correct 316 ms 57720 KB Output is correct
9 Correct 426 ms 53740 KB Output is correct
10 Correct 528 ms 56708 KB Output is correct
11 Correct 366 ms 59180 KB Output is correct
12 Correct 349 ms 55544 KB Output is correct
13 Correct 398 ms 56192 KB Output is correct
14 Correct 467 ms 57240 KB Output is correct
15 Correct 65 ms 17400 KB Output is correct
16 Correct 266 ms 54364 KB Output is correct
17 Correct 3462 ms 266356 KB Output is correct
18 Correct 3029 ms 265344 KB Output is correct
19 Correct 2386 ms 268032 KB Output is correct
20 Correct 3233 ms 269144 KB Output is correct
21 Correct 4304 ms 271776 KB Output is correct
22 Correct 3003 ms 270868 KB Output is correct
23 Correct 2971 ms 270940 KB Output is correct
24 Correct 2551 ms 271144 KB Output is correct
25 Correct 1778 ms 270060 KB Output is correct
26 Correct 2436 ms 270460 KB Output is correct
27 Correct 93 ms 23160 KB Output is correct
28 Correct 300 ms 64120 KB Output is correct
29 Correct 316 ms 65656 KB Output is correct
30 Runtime error 26 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -