結果

問題 No.2662 Installing Cell Towers
ユーザー ymmtr(せるたわーしーぷ!)ymmtr(せるたわーしーぷ!)
提出日時 2023-03-03 22:20:06
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,850 bytes
コンパイル時間 1,742 ms
コンパイル使用メモリ 172,392 KB
実行使用メモリ 6,548 KB
最終ジャッジ日時 2024-03-16 01:59:56
合計ジャッジ時間 8,884 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,548 KB
testcase_01 AC 2 ms
6,548 KB
testcase_02 AC 2 ms
6,548 KB
testcase_03 TLE -
testcase_04 AC 9 ms
6,548 KB
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

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