結果

問題 No.3284 Picnic with Friends
ユーザー pockyny
提出日時 2025-10-03 08:58:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,581 bytes
コンパイル時間 1,334 ms
コンパイル使用メモリ 110,372 KB
実行使用メモリ 27,616 KB
最終ジャッジ日時 2025-10-03 08:59:37
合計ジャッジ時間 83,361 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

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;
    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 = upper_bound(b.begin(),b.end(),le) - b.begin();
            int r_id = upper_bound(b.begin(),b.end(),ri) - b.begin();
            // 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