oj.uz

Submission #705896

# Submission time Handle Problem Language Result Execution time Memory
705896 2023-03-05T15:40:33 Z safaricola Railway Trip 2 (JOI22_ho_t4) C++17
11 / 100
 2000 ms 340944 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,t[20][N][2],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[20];// 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[20];// 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,18){
		lroot[j-1]=new node(1,n+1);
		rroot[j-1]=new nodee(1,n+1);
		rep(i,n)lroot[j-1]->upd(i,i,i); //0 trains
		rep(i,n)rroot[j-1]->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,17){
		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=17; 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 5 ms 1236 KB Output is correct
2 Correct 5 ms 1360 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Incorrect 4 ms 1224 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1236 KB Output is correct
2 Correct 5 ms 1360 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Incorrect 4 ms 1224 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 1836 ms 339412 KB Output is correct
2 Correct 1802 ms 339376 KB Output is correct
3 Correct 1957 ms 339576 KB Output is correct
4 Correct 1807 ms 339380 KB Output is correct
5 Correct 1820 ms 340880 KB Output is correct
6 Correct 1806 ms 340772 KB Output is correct
7 Correct 1888 ms 340516 KB Output is correct
8 Correct 1714 ms 336244 KB Output is correct
9 Correct 1699 ms 339620 KB Output is correct
10 Correct 1761 ms 340776 KB Output is correct
11 Correct 1789 ms 340828 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 339896 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 340944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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