# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
388728 | 2021-04-12T17:22:04 Z | victoriad | Fountain (eJOI20_fountain) | C++14 | 545 ms | 524292 KB |
#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; int search(int l,vector<pair<long long int,int> >&v){ int low=0,hi=v.size(),r=-1,mid; while(low<=hi){ mid=low+(hi-low)/2; if(v[mid].first>=l){ r=v[mid].second; hi=mid-1; } else{ low=mid+1; } } if(r==-1)return 0; else return r+1; } void grupos(int nodo,vector<long long int>&d,vector<vector<pair<long long int, int> > >& c, vector<long long int>& v){ int max=d[nodo]; long long int x=0; vector<pair<long long int,int> >a; for(int i=nodo+1;i<d.size();i++){ if(d[i]>max){ max=d[i]; x+=v[i]; a.push_back(make_pair(x,i)); } } c[nodo]=a; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int n,q; cin>>n>>q; int vo,r,l; vector<long long int>v(n); vector<long long int>d(n); cin>>d[0]>>v[0]; for(int i=1;i<n;i++){ cin>>d[i]>>v[i]; } vector<vector<pair<long long int, int> > >c(n); vector<bool>p(n,false); for(int i=0;i<n;i++){ grupos(i,d,c,v); } for(int i=0;i<q;i++){ cin>>r>>l; r--; l-=v[r]; if(l<=0)cout<<r+1<<"\n"; else{ if(c[r].size()==0)cout<<0<<"\n"; else cout<<search(l,c[r])<<"\n"; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 460 KB | Output is correct |
3 | Correct | 1 ms | 460 KB | Output is correct |
4 | Correct | 2 ms | 588 KB | Output is correct |
5 | Correct | 9 ms | 8140 KB | Output is correct |
6 | Correct | 5 ms | 3056 KB | Output is correct |
7 | Correct | 2 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 545 ms | 524292 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 460 KB | Output is correct |
3 | Correct | 1 ms | 460 KB | Output is correct |
4 | Correct | 2 ms | 588 KB | Output is correct |
5 | Correct | 9 ms | 8140 KB | Output is correct |
6 | Correct | 5 ms | 3056 KB | Output is correct |
7 | Correct | 2 ms | 332 KB | Output is correct |
8 | Runtime error | 545 ms | 524292 KB | Execution killed with signal 9 |
9 | Halted | 0 ms | 0 KB | - |