Submission #409131

#TimeUsernameProblemLanguageResultExecution timeMemory
409131victoriadFountain (eJOI20_fountain)C++14
100 / 100
420 ms31736 KiB
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <utility> #include <queue> #include <map> #include <iomanip> #include <stack> #include <fstream> using namespace std; vector<int>v; vector<int>d; vector<vector<int> >up; int search(int l,vector<int>&ps,int r){ int low=0,hi=18,mid,re=-1; while(low<=hi){ mid=low+(hi-low)/2; if(ps[up[r][mid]]>l){ low=mid+1; re=mid; } else{ hi=mid-1; } } if(re==-1)return 0; if(ps[up[r][1]]<=l)return up[r][re]+1; return search(l,ps,up[r][re]); } void suma(vector<int>&ps,vector<vector<int> >&c,int nodo){ if(up[nodo][1]==-1)ps[nodo]=v[nodo]; else ps[nodo]=ps[up[nodo][1]]+v[nodo]; for(int y:c[nodo]){ suma(ps,c,y); } } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int n,q; cin>>n>>q; int l,r; v.resize(n); d.resize(n); for(int i=0;i<n;i++){ cin>>d[i]>>v[i]; } vector<vector<int> >con(n); up.resize(n); vector<int>a(28,-1); for(int i=0;i<n;i++)up[i]=a; for(int i=0;i<n;i++)up[i][0]=i; int an=-1,u=0; up[n-1][1]=-1; int x=d[n-1]; priority_queue<pair<int,int> >pq; pq.push(make_pair(1e9-d[0],0)); for(int i=1;i<n-1;i++){ while(!pq.empty()){ int p=pq.top().first; int k=pq.top().second; if(p>1e9-d[i]){ up[k][1]=i; con[i].push_back(k); pq.pop(); } else{ break; } } pq.push(make_pair(1e9-d[i],i)); } vector<int>ps(n,0); for (int i=0;i<n;i++){ if(up[i][1]==-1){ suma(ps,con,i); } } for(int l=2;l<18;l++){ for(int i=0;i<n;i++){ if(up[i][l-1]!=-1)up[i][l]=up[up[i][l-1]][l-1]; } } for(int i=0;i<q;i++){ cin>>r>>l; r--; if(l<=v[r])cout<<r+1<<"\n"; else if(ps[r]-l<0)cout<<0<<"\n"; else cout<<search(ps[r]-l,ps,r)<<"\n"; } return 0; }

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:56:9: warning: unused variable 'an' [-Wunused-variable]
   56 |     int an=-1,u=0;
      |         ^~
fountain.cpp:56:15: warning: unused variable 'u' [-Wunused-variable]
   56 |     int an=-1,u=0;
      |               ^
fountain.cpp:58:9: warning: unused variable 'x' [-Wunused-variable]
   58 |     int x=d[n-1];
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...