結果

問題 No.1008 Bench Craftsman
コンテスト
ユーザー どらら
提出日時 2020-03-06 23:40:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,046 bytes
コンパイル時間 1,696 ms
コンパイル使用メモリ 174,784 KB
実行使用メモリ 7,132 KB
最終ジャッジ日時 2024-10-14 10:12:45
合計ジャッジ時間 18,584 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

bool check(ll c, const vector<int>& v, const vector<pair<int,int>>& w){
  if(c == -1) return false;

  vector<ll> base(v.size()+1, 0);
  vector<ll> imos(v.size()+1, 0);
  vector<ll> diff(v.size()+1, 0);

  rep(i,w.size()){
    int j = w[i].first;
    ll k = w[i].second;

    int lhs_i, rhs_i;
    ll lhs_w, rhs_w;

    {
      int lb = 0, ub = v.size();
      while(ub-lb>1){
        int mid = (lb+ub)/2;
        
        if(j-mid<0) ub = mid;
        else{
          if(k-c*mid<0) ub = mid;
          else lb = mid;
        }
      }
      lhs_i = j-lb;
      lhs_w = k-c*lb;
    }
    {
      int lb = 0, ub = v.size();
      while(ub-lb>1){
        int mid = (lb+ub)/2;
        
        if(j+mid>=v.size()) ub = mid;
        else{
          if(k-c*mid<0) ub = mid;
          else lb = mid;
        }
      }
      rhs_i = j+lb;
      rhs_w = k-c*lb;
    }

    base[lhs_i] += lhs_w;
    imos[lhs_i] += c;
    imos[j] -= c;

    imos[j] -= c;
    imos[rhs_i] += c;
    base[rhs_i+1] -= rhs_w;
  }

  ll imos_base = 0;
  rep(i,imos.size()){
    imos_base += imos[i];
    diff[i] = imos_base;
  }


  bool flg = true; 
  ll ww = 0;
  rep(i,v.size()){
    ww += base[i];
    if(v[i]<=ww) flg = false;
    ww += diff[i];
  }
  
  return flg;
}


int main(){
  int N, M;
  cin >> N >> M;
  vector<int> v;
  rep(i,N){
    int a;
    cin >> a;
    v.push_back(a);
  }
  bool flg = true;
  vector<pair<int,int>> w;
  rep(i,M){
    int a, b;
    cin >> a >> b;
    a--;
    if(v[a] <= b) flg = false;
    w.emplace_back(a,b);
  }

  if(!flg){
    cout << -1 << endl;
    return 0;
  }

  ll lb=-1, ub=1e17;
  while(ub-lb>1){
    ll mid = (lb+ub)/2;
    if(!check(mid, v, w)) lb = mid;
    else ub = mid;
  }
  
  cout << ub << endl;
  
  return 0;
}
0