第二回 アルゴリズム実技検定 N問題 - ビルの建設

Source

第二回 アルゴリズム実技検定
問題文

問題概要

省略

解法

省略

cLayversion 20201229-1)のコード

C++に変換後のコードはこちら

int N, Q, X1[5d4], Y1[5d4], D[5d4], C[5d4], A[1d5], B[1d5];

int nn, x[2d5], y[2d5], c[2d5];

int arr[2d5], xs;
int ind[1d5];
ll res[1d5];
{
  int i, j = 0;
  fenwick<ll> t;

  rd(N,Q,(X1,Y1,D,C)(N),(A,B)(Q));

  rep(i,N){
    arrInsert(nn, nn, x, X1[i], y, Y1[i], c, C[i]);
    arrInsert(nn, nn, x, X1[i] + D[i] + 1, y, Y1[i], c, -C[i]);
    arrInsert(nn, nn, x, X1[i], y, Y1[i] + D[i] + 1, c, -C[i]);
    arrInsert(nn, nn, x, X1[i] + D[i] + 1, y, Y1[i] + D[i] + 1, c, C[i]);
  }
  xs = coordcomp(nn, x, Q, A);

  t.walloc(xs, 1);
  rep(i,Q) ind[i] = i;
  sortA(Q, B, A, ind);
  sortA(nn, y, x, c);

  rep(i,Q){
    while(j < nn && B[i] >= y[j]){
      t.add(x[j], c[j]);
      j++;
    }
    res[ind[i]] = t.get(A[i]);
  }

  wtLn(res(Q));
}

Current time: 2021年09月25日01時15分18秒
Last modified: 2021年01月02日17時04分57秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: