結果

問題 No.3284 Picnic with Friends
コンテスト
ユーザー pockyny
提出日時 2025-10-03 09:03:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,607 ms / 7,000 ms
コード長 1,826 bytes
コンパイル時間 1,309 ms
コンパイル使用メモリ 110,332 KB
実行使用メモリ 47,112 KB
最終ジャッジ日時 2025-10-08 17:10:14
合計ジャッジ時間 25,135 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int i,n; cin >> n;
    vector<ll> s(n);
    for(i=0;i<n;i++) cin >> s[i];
    int q; cin >> q;
    vector<ll> v;
    ll sum = 0,las = 0;
    for(i=0;i<q;i++){
        ll t,f; cin >> t >> f;
        if(las<t){
            if(sum) v.push_back(sum);
            las = t + f;
            sum = f;
        }else{
            sum += f;
            las += f;
        }
    }
    v.push_back(sum);
    vector<pair<ll,ll>> a(n);
    vector<ll> b(n),imo(n + 1);
    for(i=0;i<n;i++) a[i] = {s[i],i};
    sort(a.begin(),a.end());
    for(i=0;i<n;i++) b[i] = a[i].first;
    const int B = 5000000;
    vector<int> cashed(B + 1);
    int j = 0;
    for(i=0;i<=B;i++){
        while(j<n && b[j]<=i) j++;
        cashed[i] = j;
    }
    auto ubId = [&](ll val){
        if(val<=B) return cashed[val];
        int id = upper_bound(b.begin(),b.end(),val) - b.begin();
        return id;
    };
    for(ll x:v){
        // cout << " x  == " << x << "\n";
        ll y = 1;
        // floor(x/z) = y なるzの範囲
        // y<=x/z<y + 1 → x/(y + 1)<z<=x/y → floor(x/(y + 1))<z<=floor(x/y)
        while(y>0){
            // cout << "y == " << y << endl;
            ll le = x/(y + 1),ri = x/y;
            // cout << "(" << le << "," << ri << "] " << endl;
            int l_id = ubId(le);
            int r_id = ubId(ri);
            // cout << l_id << " " << r_id << "\n";
            imo[l_id] += y; imo[r_id] -= y;
            if(le==0) break;
            y = x/le;
        }
    }
    for(i=1;i<=n;i++) imo[i] += imo[i - 1];
    vector<ll> ans(n);
    for(i=0;i<n;i++) ans[a[i].second] = imo[i];
    for(i=0;i<n;i++) cout << ans[i] << "\n";
}
0