Submission #1247706

#TimeUsernameProblemLanguageResultExecution timeMemory
1247706sean503Brunhilda’s Birthday (BOI13_brunhilda)C++20
3.33 / 100
1106 ms246300 KiB
#include<iostream> #include<vector> #include<cstdlib> #include<string> #include<algorithm> #include<set> #include<math.h> #include<map> #include<deque> #include<unordered_map> #include<iomanip> #include<queue> #include<array> #include<climits> #include<cstring> #include<unordered_set> #include<cstdint> #include<typeinfo> #include <random> using namespace std; #define int long long const int MAX = 1e7+1; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin>>n>>m; vector<int> v(MAX,1); set<pair<int,int>> s; int biggest = 0; for(int i = 0; i<n; i++){ int x; cin>>x; biggest = max(biggest,x); int temp = x; while(temp < MAX){ if(s.size() != 0){ pair<int,int> idk = *s.rbegin(); if(temp > idk.first){ s.insert({temp,x}); continue; } pair<int,int> it = *s.upper_bound({temp,-1}); if(it.first == temp && it.second < x){ s.erase(it); }else if(it.first == temp && it.second > x){ continue; } } s.insert({temp,x}); temp += x; } } multiset<int> ms; priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> pq; for(int i = 2; i<MAX; i++){ while(!pq.empty() && pq.top().first <= i){ ms.erase(ms.find(pq.top().second)); pq.pop(); } if(i < biggest){ v[i] = 1; }else if(ms.size() == 0){ v[i] = -1; }else{ v[i] = *ms.begin() + 1; } pair<int,int> it = *s.upper_bound({i,-1}); if(it.first == i){ ms.insert(v[i]); pq.push({it.second + i,v[i]}); } } for(int i = 0; i<m; i++){ int x; cin>>x; if(v[x] == -1){ cout<<"oo"<<"\n"; continue; } cout<<v[x]<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...