oj.uz

답안 #651595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
651595 2022-10-19T12:01:38 Z inksamurai Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 41664 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);
	}
};

struct dat{
	int l,r,id;
	dat(int _l=-1,int _r=-1,int _id=-1):
	l(_l),r(_r),id(_id){}
	bool operator<(const dat&a)const{
		return tuple<int,int,int>(a.r,a.l,a.id)<tuple<int,int,int>(r,l,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(ln);
	rep(j,ln){
		segs[j].init(si);
	}
	{
		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));
		}
	}
	// 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 ngo=go,pok=go<=need;
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1565 ms 26436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Correct 7 ms 464 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 8 ms 596 KB Output is correct
8 Correct 6 ms 596 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Correct 7 ms 464 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 8 ms 596 KB Output is correct
8 Correct 6 ms 596 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 7 ms 468 KB Output is correct
13 Correct 7 ms 484 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 8 ms 596 KB Output is correct
17 Correct 7 ms 608 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1251 ms 4556 KB Output is correct
20 Correct 1239 ms 4604 KB Output is correct
21 Correct 720 ms 5264 KB Output is correct
22 Correct 418 ms 5344 KB Output is correct
23 Correct 236 ms 6340 KB Output is correct
24 Correct 66 ms 6320 KB Output is correct
25 Correct 1008 ms 5636 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Correct 7 ms 464 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 8 ms 596 KB Output is correct
8 Correct 6 ms 596 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 460 KB Output is correct
13 Correct 8 ms 468 KB Output is correct
14 Correct 7 ms 524 KB Output is correct
15 Correct 6 ms 468 KB Output is correct
16 Correct 8 ms 596 KB Output is correct
17 Correct 8 ms 584 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1099 ms 23672 KB Output is correct
20 Correct 1084 ms 23488 KB Output is correct
21 Correct 992 ms 24112 KB Output is correct
22 Correct 1113 ms 41664 KB Output is correct
23 Correct 1071 ms 41640 KB Output is correct
24 Correct 1191 ms 41640 KB Output is correct
25 Correct 42 ms 6228 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1549 ms 26436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1565 ms 26436 KB Time limit exceeded
3 Halted 0 ms 0 KB -