Submission #581001

#TimeUsernameProblemLanguageResultExecution timeMemory
581001juggernautEvent Hopping (BOI22_events)C++14
40 / 100
1588 ms99276 KiB
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; typedef long long ll; typedef long double ld; #define USING_ORDERED_SET 0 #if USING_ORDERED_SET #include<bits/extc++.h> using namespace __gnu_pbds; template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; #endif template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef juggernaut #define printl(args...) printf(args) #else #define printl(args...) 0 #endif int n,q; pair<int,int>a[100005]; bool cmp(pair<pair<int,int>,int>l,pair<pair<int,int>,int>r){ if(l.fr.sc==r.fr.sc)return l.fr.fr<r.fr.fr; return l.fr.sc<r.fr.sc; } int dp[5005][5005]; int lf[100005]; pair<pair<int,int>,int>b[100005]; const int inf=1e9; int pos[100005]; int fen[100005]; void update(int pos,int val){ while(pos<=n+2){ umin(fen[pos],val); pos+=(pos&-pos); } } int query(int pos){ int ans=inf; while(pos){ umin(ans,fen[pos]); pos-=(pos&-pos); } return ans; } int dp2[100005]; int main(){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++)scanf("%d%d",&a[i].fr,&a[i].sc); for(int i=1;i<=n;i++)b[i]=make_pair(a[i],i); sort(b+1,b+1+n,cmp); for(int i=1;i<=n;i++)pos[b[i].sc]=i; for(int i=1;i<=n;i++){ int l=1,r=i; while(l<r){ int mid=(l+r)>>1; if(b[i].fr.fr<=b[mid].fr.sc)r=mid; else l=mid+1; } lf[i]=l; } if(n<=5000){ for(int i=0;i<5005;i++) for(int j=0;j<5005;j++)dp[i][j]=inf; for(int i=1;i<=n;i++){ dp[i][i]=0; for(int j=1;j<=n+2;j++)fen[j]=inf; update(n-i+1,0); for(int j=i+1;j<=n;j++){ dp[i][j]=query(n-lf[j]+1)+1; //for(int k=lf[j];k<=n;k++)umin(dp[i][j],dp[i][k]+1); update(n-j+1,dp[i][j]); } } while(q--){ int x,y; scanf("%d%d",&x,&y); if(x==y){ puts("0"); continue; } if(a[y].fr<=a[x].sc&&a[x].sc<=a[y].sc){ puts("1"); continue; } if(dp[pos[x]][pos[y]]>=inf)puts("impossible"); else printf("%d\n",dp[pos[x]][pos[y]]); } return 0; }else{ while(q--){ int x,y; scanf("%d%d",&x,&y); if(x==y){ puts("0"); continue; } if(a[y].fr<=a[x].sc&&a[x].sc<=a[y].sc){ puts("1"); continue; } x=pos[x]; y=pos[y]; for(int i=1;i<=n;i++)dp2[i]=inf; dp2[x]=0; for(int j=1;j<=n+2;j++)fen[j]=inf; update(n-x+1,0); for(int j=x+1;j<=y;j++){ dp2[j]=query(n-lf[j]+1)+1; update(n-j+1,dp2[j]); } if(dp2[y]>=inf)puts("impossible"); else printf("%d\n",dp2[y]); } return 0; } return 1; }

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
events.cpp:49:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  for(int i=1;i<=n;i++)scanf("%d%d",&a[i].fr,&a[i].sc);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:77:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |    scanf("%d%d",&x,&y);
      |    ~~~~~^~~~~~~~~~~~~~
events.cpp:93:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |    scanf("%d%d",&x,&y);
      |    ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...