oj.uz

Submission #705904

# Submission time Handle Problem Language Result Execution time Memory
705904 2023-03-05T15:47:47 Z safaricola Railway Trip 2 (JOI22_ho_t4) C++17
11 / 100
 2000 ms 320056 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
#define rep(i,n) for (int i = 1; i <= n; i++) 
#define f first
#define s second
#define pb push_back
#define debug(x) cout<<#x<<" is "<<x<<endl;
const int N=100010;// log is <17
int n,m,k,A,B,q;
struct node{
	int s,e,m,v,lazy;
	node *l, *r;
	node(int S, int E){
		s=S,e=E,m=(s+e)/2;
		v=1e9;lazy=1e9;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void prop(){
		if(lazy==1e9)return;
		v=min(lazy, v);
		if(s!=e){
			l->lazy= min(l->lazy, v);
			r->lazy= min(r->lazy, v);
		}
		lazy=1e9;
	}
	void upd(int S, int E, int V){
		if(s==S &&e==E) lazy= V;
		else{
			if(E<=m)l->upd(S,E,V);
			else if(S>m) r->upd(S,E,V);
			else{
				l-> upd(S,m,V);
				r->upd(m+1,E,V);
			}
			l-> prop();
			r->prop();
			v=min(l->v, r->v);
		}
	}
	int rmin(int S, int E){
		prop();
		if(s==S&&e==E){
			return v;
		}
		if(E<=m)return l->rmin(S,E);
		if(S>m) return r->rmin(S,E);
		return min(l-> rmin(S,m), r->rmin(m+1,E));
	}
}*lroot[19];// stores minpos you can go from i using 1 train
struct nodee{
	int s,e,m,v,lazy;
	nodee *l, *r;
	nodee(int S, int E){
		s=S,e=E,m=(s+e)/2;
		v=0;lazy=0;
		if(s!=e){
			l = new nodee(s,m);
			r=new nodee(m+1,e);
		}
	}
	void prop(){
		if(lazy==0)return;
		//debug (lazy) debug(v) debug(s) debug(e);
		if(s!=e){
			l->lazy= max(l->lazy, lazy);
			r->lazy= max(r->lazy, lazy);
		}
		v=max(lazy, v);
		lazy=0;
	}
	void upd(int S, int E, int V){
		if(s==S &&e==E) lazy= V;
		else{
			if(E<=m)l->upd(S,E,V);
			else if(S>m) r->upd(S,E,V);
			else{
				l-> upd(S,m,V);
				r->upd(m+1,E,V);
			}
			l-> prop();
			r->prop();
			v=max(l->v, r->v);
		}
	}
	int rmax(int S, int E){
		prop();
		//cout<<s<<' '<<e<<' '<<v<<endl;
		if(s==S&&e==E){
			return v;
		}
		if(E<=m)return l->rmax(S,E);	
		if(S>m) return r->rmax(S,E);
		return max(l-> rmax(S,m), r->rmax(m+1,E));
	}
}*rroot[19];// stores maxpos you can go from i using 1 train
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k>>m;
	rep(j,17){
		lroot[j-1]=new node(1,n+1);
		rroot[j-1]=new nodee(1,n+1);
	}
	rep(i,n)lroot[0]->upd(i,i,i);
	rep(i,n)rroot[0]->upd(i,i,i);
	//store value for 1 train
	rep(i,m){
		cin>>A>>B;
		if(A>B){
			//right to left, min
			lroot[0]->upd(max(1,A-k+1),A,B);
		}else{
			// left to right, max
			rroot[0]->upd(A,min(n, A+k-1), B);
			//hopefully rroot is correct
		}
	}
	//rep(i,n)cout<<lroot[0]->rmin(i,i)<<' ';cout<<endl;
	//rep(i,n)cout<<rroot[0]->rmax(i,i)<<' ';cout<<endl;
	rep(j,16){
		rep(i,n){
			int leftt=lroot[j-1]->rmin(i,i), rightt=rroot[j-1]->rmax(i,i);
			lroot[j]->upd(i,i,lroot[j-1]->rmin(leftt,rightt));
			rroot[j]->upd(i,i,rroot[j-1]->rmax(leftt,rightt));
		}
		//rep(i,n)cout<<lroot[0]->rmin(i,i)<<' ';cout<<endl;
		//rep(i,n)cout<<rroot[0]->rmax(i,i)<<' ';cout<<endl;
	}
	
	cin>>q;
	rep(loopp,q){
		cin>>A>>B;
		int ans=0, leftt=A, rightt=A, lef, rig;
		//cout<<t[0][A][1]<<endl;
		for(int i=16; i>=0; i--){
			lef=lroot[i]->rmin(leftt, rightt);
			rig=rroot[i]->rmax(leftt, rightt);
			if (!(lef <= B && B <= rig)){
                ans += (1<<i);
				leftt=lef; rightt=rig;
            }
		}
		lef=lroot[0]->rmin(leftt, rightt);
		rig=rroot[0]->rmax(leftt, rightt);
		if(lef <= B && B <= rig)cout<<ans+1<<'\n';
		else cout<<-1<<'\n';
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1236 KB Output is correct
2 Correct 4 ms 1272 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Incorrect 3 ms 1236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1236 KB Output is correct
2 Correct 4 ms 1272 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Incorrect 3 ms 1236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1394 ms 319752 KB Output is correct
2 Correct 1376 ms 319672 KB Output is correct
3 Correct 1523 ms 319692 KB Output is correct
4 Correct 1303 ms 319672 KB Output is correct
5 Correct 1442 ms 319676 KB Output is correct
6 Correct 1409 ms 319672 KB Output is correct
7 Correct 1356 ms 319684 KB Output is correct
8 Correct 1274 ms 316484 KB Output is correct
9 Correct 1342 ms 319620 KB Output is correct
10 Correct 1324 ms 319604 KB Output is correct
11 Correct 1277 ms 319680 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 320056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 319804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1236 KB Output is correct
2 Correct 4 ms 1272 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Incorrect 3 ms 1236 KB Output isn't correct
5 Halted 0 ms 0 KB -