Submission #1176299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176299		8pete8	Event Hopping (BOI22_events)	C++20	100 / 100	222 ms	86964 KiB

events

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod=1e9+7,mxn=4e5,inf=1e18,minf=-1e18,lg=30,Mxn=1e6;
//#undef int
int n,k,m,d,q,T;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
int go[mxn+10][lg+1],back[mxn+10][lg+1];
int back2[mxn+10][lg+1];
struct seg{
	pii v[2*mxn+10];
	void init(){for(int i=0;i<=4*n;i++)v[i]={inf,inf};}
	void update(int pos,int val,int id){
		pos+=2*n;
		v[pos]=min(v[pos],{val,id});
		for(int i=pos;i>0;i>>=1)v[i>>1]=min(v[i],v[i^1]);
	}
	pii qry(int l,int r){
		pii ans={inf,inf};
		for(l+=2*n,r+=2*n;l<=r;l>>=1,r>>=1){
			if(l&1)ans=min(ans,v[l++]);
			if(!(r&1))ans=min(ans,v[r--]);
		}
		return ans;
	}
}t;
pii pref[mxn+10];
int32_t main(){
	fastio
	cin>>n>>q;
	vector<int>comp;
	vector<pii>event(n);
	for(auto &i:event){
		cin>>i.f>>i.s;
		comp.pb(i.f);
		comp.pb(i.s);
	}
	sort(all(comp));
	comp.erase(unique(all(comp)),comp.end());
	for(auto &i:event){
		i.f=lb(all(comp),i.f)-comp.begin();
		i.s=lb(all(comp),i.s)-comp.begin();
	}
	t.init();
	for(int i=0;i<comp.size();i++)back[i][0]=inf;
	int c=0;
	for(auto i:event){
		pref[i.f]=max(pref[i.f],{i.s,c});
		t.update(i.s,i.f,c);
		c++;
	}
	for(int i=1;i<comp.size();i++)pref[i]=max(pref[i-1],pref[i]);
	for(int i=0;i<n;i++)go[i][0]=pref[event[i].s].s;
	c=0;
	for(auto i:event){
		back[c][0]=t.qry(i.f,i.s).s;
		c++;
	}
	for(int j=1;j<=lg;j++){
		for(int i=0;i<n;i++){
			back[i][j]=back[back[i][j-1]][j-1];
			go[i][j]=go[go[i][j-1]][j-1];
		}
	}
	while(q--){
		int a,b;cin>>a>>b;
		a--,b--;
		if(a==b){
			cout<<0<<'\n';
			continue;
		}
		if(event[b].f<=event[a].s&&event[a].s<=event[b].s){
			cout<<1<<'\n';
			continue;
		}
		if(event[a].s>=event[b].f)cout<<"impossible\n";
		else{
			int cur=a,ans=0,cur2=b;
			for(int i=lg;i>=0;i--){
				if(event[go[cur][i]].s>event[cur].s&&event[go[cur][i]].s<event[cur2].f)cur=go[cur][i],ans+=(1LL<<i);
			}
			for(int i=lg;i>=0;i--){
				if(event[back[cur2][i]].f<event[cur2].f&&event[back[cur2][i]].f>event[cur].s)cur2=back[cur2][i],ans+=(1LL<<i);
			}
			if(event[back[cur2][0]].f<=event[cur].s)cout<<ans+2<<'\n';
			else cout<<"impossible\n";
		}
	}
}

Compilation message (stderr)

events.cpp:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   16 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
events.cpp:23:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   23 | void setIO(string name){
      |                       ^
events.cpp:32:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   32 |         void init(){for(int i=0;i<=4*n;i++)v[i]={inf,inf};}
      |                   ^
events.cpp:33:43: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   33 |         void update(int pos,int val,int id){
      |                                           ^
events.cpp:38:28: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 |         pii qry(int l,int r){
      |                            ^
events.cpp:48:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   48 | int32_t main(){
      |              ^
events.cpp: In function 'void setIO(std::string)':
events.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30