fork download
copy 
  1. //ojou kawayo no.1
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define tsk "vaccination"
  5. #define pb push_back
  6. #define pf push_front
  7. #define fi first
  8. #define se second
  9. #define Ningen_sama signed
  10. #define tachi main()
  11. #define __builtin_popcount __builtin_popcountll
  12. #define el cout<<'\n'
  13. #define all(a) a.begin(),a.end()
  14. #define invAll(a) a.rbegin(),a.rend()
  15. #define sz(a) ((int)a.size())
  16. #define BIT(x, k) (1ll&((x) >> (k)))
  17. #define mem(a,x) memset(a,x,sizeof(a))
  18. #define debug(x) cout << #x << " = " << x << '\n'
  19. #define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
  20. #define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
  21. #define FORD(i, l, r) for(int i = (l); i >= (r); --i)
  22. #define REP(i, n) for(int i = 0; i < (n); ++i)
  23. //#define int long long
  24.  
  25. template<class T> bool maximize(T& u, T v){if(u >= v) return false;return u = v, true;}
  26. template<class T> bool minimize(T& u, T v){if(u <= v) return false;return u = v, true;}
  27.  
  28. using pii = pair<int, int>;
  29. using ll = long long;
  30. using vi = vector<int>;
  31. using vpii = vector<pair<int, int>>;
  32.  
  33. #define inf32 0x3f3f3f3f
  34. #define inf64 0x3f3f3f3f3f3f3f3f
  35. const int maxn = 1e6+5;
  36. const int N = 5e3 + 5;
  37. const int base = 31;
  38. const ll mod = 1e9 + 7;
  39. const ll need = 67108863;
  40. const int vc = 2e9 + 1;
  41. const ll INF18 = 4557430888798830399;
  42. const ll LOG = 20;
  43. const double eps = 1e-9;
  44. const int BLOCK = 447;
  45. const int dx[4] = {1, 0, -1, 0};
  46. const int dy[4] = {0, -1, 0, 1};
  47.  
  48. mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
  49. #define rand rd
  50. inline long long Rand(long long L, long long R) {
  51.     if(L>R) return 0;
  52.     return L + rd() % (R - L + 1);
  53. }
  54.  
  55. inline ll add(ll x, ll y){x+=y;if(x>=mod) x-=mod;if(x<0) x+=mod;return x;}
  56. inline ll mult(ll x, ll y){return 1LL * x * y % mod;}
  57.  
  58. ll T(int a, int k) {
  59.     return (a + k - 1) / k;
  60. }
  61.  
  62. struct Node {
  63.     ll delta;
  64.     int idx;
  65.     int k;
  66. };
  67.  
  68. struct Cmp {
  69.     bool operator()(Node const& A, Node const& B) const {
  70.         if (A.delta != B.delta) return A.delta < B.delta;
  71.         return A.idx > B.idx;
  72.     }
  73. };
  74.  
  75. int n, t;
  76. int a[maxn], query[maxn], x[maxn];
  77. int Mmax;
  78.  
  79. inline void init(){
  80.  
  81. }
  82.  
  83. inline void input(){
  84.     cin >> n >> t;
  85.     FOR(i, 0, n - 1) cin >> a[i];
  86.  
  87.     FOR(i, 0, t - 1){
  88.         cin >> query[i];
  89.         Mmax = max(Mmax, query[i]);
  90.     }
  91. }
  92.  
  93. inline void solve(){
  94.     FOR(i, 0, n - 1) x[i] = 1;
  95.     ll current_total = 0;
  96.     FOR(i, 0, n - 1) current_total += T(a[i], 1);
  97.  
  98.     priority_queue<Node, vector<Node>, Cmp> pq;
  99.  
  100.     FOR(i, 0, n - 1){
  101.         ll delta = T(a[i], 1) - T(a[i], 2);
  102.         pq.push({delta, i, 1});
  103.     }
  104.  
  105.     vector<ll> ans(Mmax + 1, -1);
  106.     if (Mmax >= n) ans[n] = current_total;
  107.  
  108.     for (int s = n; s < Mmax; ++s) {
  109.         while (!pq.empty()) {
  110.             Node top = pq.top();
  111.             if (top.k != x[top.idx]) {
  112.                 pq.pop();
  113.                 continue;
  114.             }
  115.             pq.pop();
  116.             ll delta = top.delta;
  117.             int i = top.idx;
  118.             int k = top.k;
  119.  
  120.             current_total -= delta;
  121.  
  122.             x[i] = k + 1;
  123.  
  124.             ll new_delta = T(a[i], k + 1) - T(a[i], k + 2);
  125.             pq.push({new_delta, i, k + 1});
  126.             break;
  127.         }
  128.         ans[s + 1] = current_total;
  129.     }
  130.  
  131.     for (int i = 0; i < t; ++i) {
  132.         int m = query[i];
  133.         cout << ans[m]; el;
  134.     }
  135. }
  136.  
  137. Ningen_sama tachi{
  138.     //konnakiri~~
  139.     if(fopen(tsk".inp","r")){
  140.         freopen(tsk".inp","r",stdin);
  141.         freopen(tsk".out","w",stdout);
  142.     }
  143.     ios_base::sync_with_stdio(false);
  144.     cin.tie(0); cout.tie(0);
  145.  
  146.     int Yodayo = 1;
  147.  
  148.     //cin >> Yodayo;
  149.     //init();
  150.  
  151.     while(Yodayo--){
  152.         input();
  153.         solve();
  154.     }
  155.  
  156.     //execute;
  157. }
  158. //otsunakiri~~
  159.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yrBumn
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!