oj.uz

Submission #651603

# Submission time Handle Problem Language Result Execution time Memory
651603 2022-10-19T12:17:07 Z inksamurai Event Hopping (BOI22_events) C++17
25 / 100
 1500 ms 41324 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3CZAtRo ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

const int inf=1e9;

struct segtree{
	int n;
	vi seg;
	segtree(int _n=0){init(_n);}
	void init(int _n){
		n=_n;
		int si=1;
		while(si<=n) si*=2;
		si*=2;
		seg.clear();
		seg=vi(si,inf);
	}
	void set(int node,int l,int r,int pos,int x){
		if(l==r-1){
			seg[node]=x;
			return;
		}
		int m=(l+r)/2;
		if(pos<m){
			set(node*2+1,l,m,pos,x);
		}else{
			set(node*2+2,m,r,pos,x);
		}
		seg[node]=min(seg[node*2+1],seg[node*2+2]);
	}
	void set(int pos,int x){
		set(0,0,n,pos,x);
	}
	int prod(int node,int l,int r,int _l,int _r){
		if(l>=_r or r<=_l){
			// _e
			return inf;
		}
		if(_l<=l and r<=_r){
			return seg[node];
		}
		int m=(l+r)/2;
		return min(prod(node*2+1,l,m,_l,_r),prod(node*2+2,m,r,_l,_r));
	}
	int prod(int l,int r){
		return prod(0,0,n,l,r);
	}
	int get(int i){
		return prod(i,i+1);
	}
};

// int op(int l,int r){return min(l,r);}
// int e(){return inf;}

struct dat{
	int l,r,id;
	dat(int _l=-1,int _r=-1,int _id=-1):
	l(_l),r(_r),id(_id){}
};

signed main(){
_3CZAtRo;
	int n,q;
	cin>>n>>q;
	vec(dat) a(n);
	rep(i,n){
		cin>>a[i].l>>a[i].r;
		a[i].id=i;
	}
	vec(vec(pii)) qry(n);
	rep(_,q){
		int s,t;
		cin>>s>>t;
		qry[t-1].pb(pii(s-1,_));
	}

	vi tmp;
	rep(i,n){
		tmp.pb(a[i].l);
		tmp.pb(a[i].r);
	}
	sort(tmp.begin(),tmp.end());
	tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
	int si=sz(tmp);
	rep(i,n){
		a[i].l=lower_bound(tmp.begin(),tmp.end(),a[i].l)-tmp.begin();
		a[i].r=lower_bound(tmp.begin(),tmp.end(),a[i].r)-tmp.begin();
	}

	const int ln=17;
	
	vec(segtree) segs;
	rep(j,ln){
		segtree curseg(si);
		rep(i,si){
			curseg.set(i,inf);
		}
		segs.pb(curseg);
	}
	rep(i,n){
		int l=a[i].l,r=a[i].r;
		int val=segs[0].get(r);
		segs[0].set(r,min(val,l));
	}
	rng(j,1,ln){
		rep(i,n){
			int r=a[i].r;
			int l=segs[j-1].get(r);
			int val=segs[j-1].prod(l,r+1);
			int old_val=segs[j-1].get(r);
			segs[j].set(r,min(old_val,val));
		}
	}

	vec(segtree) adsegs;
	rep(j,ln){
		segtree curseg(si);
		rep(i,si){
			curseg.set(i,inf);
		}
		adsegs.pb(curseg);
	}
	rep(j,ln){
		rep(i,n){
			int r=a[i].r;
			if(j==0){
				adsegs[j].set(r,segs[j].get(r));
			}else{
				int l=adsegs[j-1].get(r);
				adsegs[j].set(r,segs[j].prod(l,r+1));
			}
		}
	}

	// print(" output points ");
	// for(auto p:a){
	// 	print(p.l,p.r);
	// }
	// print(".....");
	auto af=[&](int i,int need)->int{
		int res=1;
		int go=a[i].l;
		int r=a[i].r;
		// print(need,r);
		if(r<need) return inf;
		if(go<=need and need<=r) return 1;
		// print(segs[1].prod(go,r+1));
		// rep(_,4){
		// 	res+=1;
		// 	int ngo=segs[0].prod(go,r+1);
		// 	if(go<=need) break;
		// 	if(ngo==go) break;
		// 	go=ngo;
		// }
		// print(go);
		for(int j=ln-1;j>=0;j--){
			int pok=go<=need;
			if(j){
				int val=adsegs[j-1].prod(go,r+1);
				if(val<=need) pok=1;
			}
			// for(int nj=j-1;nj>=0;nj--){
			// 	int val=segs[nj].prod(ngo,r+1);
			// 	if(val<=need)pok=1;
			// 	ngo=val;
			// }
			if(!pok){
				res+=1<<j;
				go=segs[j].prod(go,r+1);
			}
		}
		if(go>need) return inf;
		// print(go);
		return res;
	};
	// af(5,0);
	vi pns(q,inf);
	rep(i,n){
		for(auto p:qry[i]){
			if(p.fi==i){
				pns[p.se]=0;
			}else{
				pns[p.se]=af(i,a[p.fi].r);
			}
		}
	}
	rep(i,q){
		if(pns[i]==inf){
			cout<<"impossible\n";
		}else{
			cout<<pns[i]<<"\n";
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1595 ms 41308 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 12 ms 648 KB Output is correct
4 Correct 12 ms 596 KB Output is correct
5 Correct 12 ms 596 KB Output is correct
6 Correct 11 ms 652 KB Output is correct
7 Correct 14 ms 852 KB Output is correct
8 Correct 13 ms 852 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 12 ms 648 KB Output is correct
4 Correct 12 ms 596 KB Output is correct
5 Correct 12 ms 596 KB Output is correct
6 Correct 11 ms 652 KB Output is correct
7 Correct 14 ms 852 KB Output is correct
8 Correct 13 ms 852 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 14 ms 596 KB Output is correct
13 Correct 13 ms 724 KB Output is correct
14 Correct 12 ms 648 KB Output is correct
15 Correct 12 ms 576 KB Output is correct
16 Correct 18 ms 852 KB Output is correct
17 Correct 14 ms 852 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 340 ms 4728 KB Output is correct
20 Correct 305 ms 4732 KB Output is correct
21 Correct 216 ms 5436 KB Output is correct
22 Correct 151 ms 5484 KB Output is correct
23 Correct 147 ms 7536 KB Output is correct
24 Correct 111 ms 7624 KB Output is correct
25 Correct 281 ms 6904 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 12 ms 648 KB Output is correct
4 Correct 12 ms 596 KB Output is correct
5 Correct 12 ms 596 KB Output is correct
6 Correct 11 ms 652 KB Output is correct
7 Correct 14 ms 852 KB Output is correct
8 Correct 13 ms 852 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 12 ms 652 KB Output is correct
13 Correct 12 ms 648 KB Output is correct
14 Correct 12 ms 596 KB Output is correct
15 Correct 11 ms 596 KB Output is correct
16 Correct 14 ms 928 KB Output is correct
17 Correct 14 ms 920 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Execution timed out 1584 ms 40532 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1595 ms 41308 KB Time limit exceeded
3 Halted 0 ms 0 KB -