結果

問題 No.2662 Installing Cell Towers
ユーザー ymmtr(せるたわーしーぷ!)
提出日時 2023-03-03 22:20:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,850 bytes
コンパイル時間 1,692 ms
コンパイル使用メモリ 171,548 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-09-30 03:41:25
合計ジャッジ時間 7,986 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 2 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

//C - Installing Cell-Towers
//Writer解(TLEがでることの確認)
//なんかARC-Aみたい？
//一発の発想がすべて

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
using ll = long long;
#define ALL(a)  (a).begin(),(a).end()
using v_vll = vector<vector<ll>>;
vector<ll> p,a,ans_n,ans_l,imos;
ll n,m;
void naive(){
    ans_n.resize(n+1);
    for(ll i=0;i<m;i++){
        ans_n[p[i]]+=a[i];
        for(ll j=1;j<a[i];j++){
            if(p[i]+j<=n){
                ans_n[p[i]+j]+=a[i]-j;
            }
            if(1<=p[i]-j){
                ans_n[p[i]-j]+=a[i]-j;
            }
        }
    }
}
void linear(){
    //下駄を最初にはかせる
    ll geta=0;
    //geta,なんぼだけ足しますか？
    //max(0,a[i]-p[i]);
    ans_l.resize(n+1);
    //範囲外参照に注意
    for(ll i=0;i<m;i++){
        //始点
        if(p[i]-a[i]<=0){
            geta+=max(0LL,a[i]-p[i]);
            ans_l[1]++;
        }
        else{
            ans_l[p[i]-a[i]+1]++;
        }

        //中間点
        if(p[i]+1<=n){ans_l[p[i]+1]-=2;}
        
        //終端点
        if(p[i]+a[i]+1<=n){ans_l[p[i]+a[i]+1]++;}

    }//いもす法テーブル完成

    for(ll i=2;i<=n;i++){
        ans_l[i]+=ans_l[i-1];
    }
    imos=ans_l;
    ans_l[1]+=geta;
    for(ll i=2;i<=n;i++){
        ans_l[i]+=ans_l[i-1];
    }
}
int main(){
    cin>>n>>m;
    a.resize(m+1);
    p.resize(m+1);
    for(ll i=0;i<m;i++){
        cin>>p[i]>>a[i];
    }
    naive();
    for(ll i=1;i<=n;i++){
        cout<<ans_n[i]<<" ";
    }
    cout<<endl;
    return 0;
    linear();
    for(ll i=1;i<=n;i++){
        cout<<ans_l[i]<<" ";
    }
    cout<<endl;
    for(ll i=1;i<=n;i++){
        cout<<imos[i]<<" ";
    }
    cout<<endl;
    if(ans_n==ans_l){
        cout<<"AC"<<endl;
    }else{
        cout<<"WA"<<endl;
    }
}
0