結果
| 問題 | 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 | 
ソースコード
#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";
}
            
            
            
        