Submission #561646

#TimeUsernameProblemLanguageResultExecution timeMemory
561646Omar_ElgedawyRainforest Jumps (APIO21_jumps)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "stub.cpp" using namespace std; #define cin(vec) for(auto& i : vec) cin >> i #define cout(vec) for(auto& i : vec) cout << i << " "; cout << "\n"; #define fast ios::sync_with_stdio(0);cin.tie(0); #define loop(i,a,b) for (int i = a; i < b; i++) #define F first #define S second #define pb(n) push_back(n) #define pf(n) push_front(n) #define dci(d) fixed<<setprecision(d) #define sp ' ' #define el '\n' #define all(v) v.begin(),v.end() // #define int long long int dx[8]= {0,0,1,-1,-1,1,1,-1}; int dy[8]= {-1,1,0,0,-1,1,-1,1}; int const N=2e5+5,M=1e2+1,Mod=1e9+7; template <class t>struct segtree{ const t ID=0; vector<t>seg; int n; void init(int _n){ n=_n; seg.assign(n*2,ID); } t comp(t a,t b){return max(a,b);} void pull(int p){ seg[p]=comp(seg[p*2],seg[p*2+1]); } void upd(int p,t val){ seg[p+=n]=val; for(p/=2;p;p/=2)pull(p); } t qry(int l,int r){ t ra=ID,rb=ID; for(l+=n,r+=n+1;l<r;l/=2,r/=2){ if(l&1)ra=comp(ra,seg[l++]); if(r&1)rb=comp(rb,seg[--r]); } return comp(ra,rb); } }; segtree<int>st; pair<int,int>loc[N]; int a,b,c,d,freq[N]; vector<int>adj[N]; int nn; void init(int n, vector<int> v) { ios::sync_with_stdio(0);cin.tie(0); int sz=(1<<((int)ceil(log2(n))))+1; nn=n; st.init(sz); for(int i=0;i<n;i++){ st.upd(i+1,v[i]); freq[i]=v[i]; } for(int i=0;i<n;i++){ int x=v[i]; int l=1,r=i+1,left=-1; while(l<=r){ int m=(l+r)/2; if(st.qry(m,i+1)>x){ left=m-1; l=m+1; } else { r=m-1; } } int right=-1; l=i+1,r=n; while(l<=r){ int m=(l+r)/2; if(st.qry(i+1,m)>x){ right=m-1; r=m-1; } else { l=m+1; } } if(left!=-1) left=freq[left]; if(right!=-1) right=freq[right]; loc[x]={left,right}; } for(int i=1;i<=n;i++){ if(loc[i].F!=-1)adj[i].pb(loc[i].F); if(loc[i].S!=-1)adj[i].pb(loc[i].S); } } int minimum_jumps(int A, int B, int C, int D) { a=A;b=B;c=C;d=D; queue<pair<int,int>>q; for(int i=a;i<=b;i++){ q.push({freq[i],0}); } int f[nn+1]={}; for(int i=c;i<=d;i++)f[freq[i]]=1; bool vis[nn+1]={}; while(q.size()){ int u=q.front().F; int c=q.front().S; q.pop(); vis[u]=1; if(f[u]){ return c; } for(auto j:adj[u]){ if(!vis[j])q.push({j,c+1}); } } return -1; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccbVDWpI.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccWbjksI.o:jumps.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status