結果

問題 No.3284 Picnic with Friends
ユーザー neet
提出日時 2025-09-27 06:48:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,577 bytes
コンパイル時間 3,215 ms
コンパイル使用メモリ 293,040 KB
実行使用メモリ 814,156 KB
最終ジャッジ日時 2025-09-27 06:48:18
合計ジャッジ時間 10,062 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 MLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

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;}

#pragma GCC optimize("O2")


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+1,q});
        i=j+1;
    }
    return ret;
}

int N,Q;
long S[500000];
long ans[500000+1];
vector<long> A;
pair<long,int> B[500000];

const long L=500000;
vector<pair<long,long>> C[L+1];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin>>N;
    rep(i,N)cin>>S[i];
    cin>>Q;
    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;
        }
    }
    rep(i,N) B[i]=make_pair(S[i], i);
    sort(B,B+N);

    for(long t: A){
        for(auto [l,r,x]: f(t)){
            C[min(L,l)].push_back({l,x});
            C[min(L,r)].push_back({r,-x});
        }
    }
    sort(all(C[L]));
    {
        long cur=0;
        int id=0;
        rep(j,L+1){
            for(auto [i, x]: C[j]){
                while(id<N&&B[id].fi<i) ans[B[id].se]+=cur, id++;
                cur+=x;
            }
        }
    }

    rep(i,N)cout<<ans[i]<<"\n";
}
0