結果

問題 No.3285 Chorus with Friends
ユーザー neet
提出日時 2025-09-27 06:12:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,665 bytes
コンパイル時間 3,205 ms
コンパイル使用メモリ 290,460 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-27 06:12:33
合計ジャッジ時間 5,096 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
// #include<atcoder/all>
// using mint = atcoder::modint998244353;
using ld = long double;
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename T>bool chmin(T&a,T b){return b<a?(a=b,1):0;}
template<typename T>bool chmax(T&a,T b){return b>a?(a=b,1):0;}



vector<array<long,3>> f(long N){
    vector<array<long,3>> ret;
    for(long i=1;i<=N;){
        long q=N/i;
        long j=N/q;
        ret.push_back({i,j,q});
        i=j+1;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin>>N;
    vector<long> S(N);
    rep(i,N)cin>>S[i];
    int Q;
    cin>>Q;
    vector<long> A;
    long end=0;
    rep(i,Q){
        long t,f;
        cin>>t>>f;
        if(end<t){
            A.push_back({f});
            end=t+f;
        }
        else{
            A.back()+=f;
            end+=f;
        }
    }
    vector<pair<long,int>> B(N);
    rep(i,N) B[i]=make_pair(S[i], i);
    sort(all(B));
    vector<long> sum(N+1,0);
    for(long t: A){
        if(N*20<=t){
            rep(i,N){
                sum[i]+=t/B[i].fi;
                sum[i+1]-=t/B[i].fi;
            }
        }
        else{
            for(auto [l,r,x]: f(t)){
                int li=lower_bound(all(B), make_pair(l,0))-B.begin();
                int ri=lower_bound(all(B), make_pair(r+1,0))-B.begin();
                sum[li]+=x;
                sum[ri]-=x;
            }
        }
    }
    rep(i,N)sum[i+1]+=sum[i];

    vector<long> ans(N);
    rep(i,N) ans[B[i].se]=sum[i];
    rep(i,N)cout<<ans[i]<<"\n";
}
0