結果

問題 No.2501 Maximum Inversion Number
コンテスト
ユーザー tnakao0123
提出日時 2024-06-20 15:26:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 1,390 bytes
コンパイル時間 419 ms
コンパイル使用メモリ 42,624 KB
最終ジャッジ日時 2025-02-21 23:31:52
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:38:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |   scanf("%d", &tn);
      |   ~~~~~^~~~~~~~~~~
main.cpp:42:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   42 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
main.cpp:43:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |     for (int i = 0; i < n; i++) scanf("%d", ls + i);
      |                                 ~~~~~^~~~~~~~~~~~~~
main.cpp:44:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   44 |     for (int i = 0; i < n; i++) scanf("%d", rs + i);
      |                                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 2501.cc:  No.2501 Maximum Inversion Number - yukicoder
 */

#include<cstdio>
#include<algorithm>
 
using namespace std;

/* constant */

const int MAX_N = 200000;

/* typedef */

using ll = long long;

/* global variables */

int ls[MAX_N], rs[MAX_N], cs0[MAX_N], cs1[MAX_N];

/* subroutines */

ll calc(int n, int k, int *cs = cs0) {
  ll sum = 0;
  for (int i = 0; i < n; i++) {
    cs[i] = (k < ls[i]) ? ls[i] : (k > rs[i]) ? rs[i] : k;
    sum += cs[i];
  }
  return sum;
}

/* main */

int main() {
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", ls + i);
    for (int i = 0; i < n; i++) scanf("%d", rs + i);

    ll lsum = 0, rsum = 0;
    for (int i = 0; i < n; i++) lsum += ls[i], rsum += rs[i];
    if (lsum > m || rsum < m) { puts("-1"); continue; }

    int k0 = 0, k1 = 1000000000 + 1;
    while (k0 + 1 < k1) {
      int k = (k0 + k1) / 2;
      if (calc(n, k) >= m) k1 = k;
      else k0 = k;
    }

    ll s0 = calc(n, k0, cs0);
    ll s1 = calc(n, k1, cs1);
    //printf(" %d,%lld %d,%lld\n", k0, s0, k1, s1);

    for (int i = 0; s1 > m && i < n; i++)
      if (cs0[i] < cs1[i]) cs1[i]--, s1--;

    ll sum = 0, f = 0;
    for (int i = n - 1; i >= 0; i--) {
      sum += f * cs1[i];
      f += cs1[i];
    }

    printf("%lld\n", sum);
  }
  
  return 0;
}
0