結果

問題 No.3284 Picnic with Friends
コンテスト
ユーザー pockyny
提出日時 2025-10-03 08:46:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,589 bytes
コンパイル時間 5,223 ms
コンパイル使用メモリ 109,872 KB
実行使用メモリ 23,872 KB
最終ジャッジ日時 2025-10-03 08:48:32
合計ジャッジ時間 95,627 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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> imo(n + 1);
    for(i=0;i<n;i++) a[i] = {s[i],i};
    sort(a.begin(),a.end());
    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;
            pair<ll,ll> p = {le,n + 1},q = {ri,n + 1};
            int l_id = upper_bound(a.begin(),a.end(),p) - a.begin();
            int r_id = upper_bound(a.begin(),a.end(),q) - a.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