제출 #1176297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176297		8pete8	Event Hopping (BOI22_events)	C++20	55 / 100	318 ms	129220 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{
	int v[2*mxn+10];
	void init(){for(int i=0;i<=4*n;i++)v[i]=inf;}
	void update(int pos,int val){
		pos+=2*n;
		v[pos]=min(v[pos],val);
		for(int i=pos;i>0;i>>=1)v[i>>1]=min(v[i],v[i^1]);
	}
	int qry(int l,int r){
		int ans=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;
int B[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;
	for(auto i:event){
		go[i.f][0]=max(go[i.f][0],i.s);
		t.update(i.s,i.f);
	}
	for(int i=1;i<comp.size();i++)go[i][0]=max(go[i][0],go[i-1][0]);
	int c=0;
	for(auto i:event){
		back[i.f][0]=min(back[i.f][0],t.qry(i.f,i.s));
		back2[c][0]=t.qry(i.f,i.s);
		c++;
	}
	for(int j=1;j<=lg;j++){
		for(int i=0;i<comp.size();i++){
			go[i][j]=go[go[i][j-1]][j-1];
			back[i][j]=((back[i][j-1]==inf)?inf:back[back[i][j-1]][j-1]);
		}
		for(int i=0;i<n;i++)back2[i][j]=((back2[i][j-1]==inf)?inf:back[back2[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=event[a].s,ans=0,cur2=event[b].f;
			for(int i=lg;i>=0;i--){
				if(go[cur][i]>cur&&go[cur][i]<cur2)cur=go[cur][i],ans+=(1LL<<i);
			}
			for(int i=lg;i>=0;i--){
				if(back2[b][i]<cur2&&back2[b][i]>cur){
					cur2=back2[b][i],ans+=(1LL<<i);
					break;
				}
			}
			if(cur2==event[b].f){
				if(back2[b][0]<=cur)cout<<ans+2<<'\n';
				else cout<<"impossible\n";
				continue;
			}
			for(int i=lg;i>=0;i--){
				if(back[cur2][i]<cur2&&back[cur2][i]>cur)cur2=back[cur2][i],ans+=(1LL<<i);
			}
			if(back[cur2][0]<=cur)cout<<ans+2<<'\n';
			else cout<<"impossible\n";
		}
	}
}

컴파일 시 표준 에러 (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;}
      |                   ^
events.cpp:33:36: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   33 |         void update(int pos,int val){
      |                                    ^
events.cpp:38:28: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 |         int 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: 0 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30