結果

問題 No.3284 Picnic with Friends
ユーザー neet
提出日時 2025-09-27 07:02:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,716 bytes
コンパイル時間 3,325 ms
コンパイル使用メモリ 288,876 KB
実行使用メモリ 765,924 KB
最終ジャッジ日時 2025-09-27 07:03:19
合計ジャッジ時間 40,262 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 MLE * 10
権限があれば一括ダウンロードができます

ソースコード

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

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

const long L=5000000;
vector<long> C[L];
vector<pair<long,long>> D;

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(long l=1;l<=t;){
            long q=t/l;
            long r=t/q+1;
            if(l<L)C[l].emplace_back(q);
            else D.emplace_back(l,q);
            if(r<L)C[r].emplace_back(-q);
            else D.emplace_back(r,-q);
            l=r;
        
        }
    }
    {
        long cur=0;
        int id=0;
        rep(i,L){
            for(auto x: C[i]){
                while(id<N&&B[id].fi<i) ans[B[id].se]+=cur, id++;
                cur+=x;
            }
        }
        for(auto [i,x]: D){
            while(id<N&&B[id].fi<i) ans[B[id].se]+=cur, id++;
            cur+=x;
        }
    }

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