ABC０６１C-Big Array

ABC061C-Big Array

問題

提出AC

#include <bits/stdc++.h>

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cout << #x << " = " << (x) << endl;
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}

const ll INF = 1LL << 60;

ll N,M,H,W,K,A,B;
string S;
//Write From this Line

int main()
{
    cout << setprecision(10);
    cin >> N >> K ;
    //a1をb1個挿入する。
    vector<ll> P(100100,0);
    //pair<入れる数、何個入ってるか>

    rep(i,N){
        ll a, b;
        cin >>  a >> b;
        P[a] += b;
    }
    ll count = 0 ;
    rep(i,100100){
        count += P[i];
        if(count>=K){
            cout <<i<<endl;
            return 0;
        }
    }

}

解法

Nの制約が<= 10⁵で、与えられる整数も<=10⁵なので、

それと同じ大きさの配列を用意してもメモリ、実行時間は問題ない。

vector P(100100,0)で

配列の大きさが100100,初期値を0として

N回の操作で入力が与えられたとき、挿入する値をa,入れる個数をbとしたときに

P.at(a)を+=bしてあげる。

でN会の挿入が終わったら、

P.at(0)からP.at(N)を見て、P.at(i)の和がKを超えたところのiを出力する。

解説も同じような解法だったので良い。