結果

問題 No.3322 引っ張りだこ
コンテスト
ユーザー のらら
提出日時 2025-08-26 18:20:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,154 bytes
コンパイル時間 3,417 ms
コンパイル使用メモリ 190,564 KB
実行使用メモリ 16,780 KB
最終ジャッジ日時 2025-10-31 20:30:28
合計ジャッジ時間 6,829 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

//貪欲マージテク(O(NlogN))
//嘘解法かもしれない
#include <iostream>
#include <algorithm>
#include <atcoder/all>
#include <queue>
using namespace std;
using namespace atcoder;
using ll = long long;
const long long INF = 1000000000000000000;
//#define endl "\n";
using classPQ = tuple<ll, ll, ll, ll, ll>;
priority_queue<classPQ, vector<classPQ>, less<classPQ>> que;

int main(){
  ll N, K;
  cin >> N >> K;
  vector<vector<ll>> A(N + 1, vector<ll>(2, 0));
  for(ll i = 1; i <= N; i++) cin >> A[i][0];
  for(ll i = 1; i <= N; i++) cin >> A[i][1];
  A[0][1] = -INF;
  
  vector<ll> l(N + 1, 0), r(N + 1, 0), tasu_a(N + 1, 0), tasu_b(N + 1, 0), selected(N + 1, 0);
  for(int i = 0; i <= N; i++){
    l[i] = i, r[i] = i;
    if(A[i][0] >= A[i][1]){
      tasu_a[i] = A[i][0];
      tasu_b[i] = A[i][1];
      selected[i] = 0;
    }else{
      tasu_a[i] = A[i][1];
      tasu_b[i] = A[i][0];
      selected[i] = 1;
    }
  }
  ll pos = 0, chg = 0, ans = 0;
  dsu d(N + 1);
  for(ll i = 1; i <= N; i++){
    if(A[i][pos] < A[i][(pos+1)%2]){
      ll ld = d.leader(i - 1);
      ans += tasu_a[ld];
      chg++;
      que.push(make_tuple(tasu_b[ld] - tasu_a[ld], ld, l[ld], r[ld], selected[ld]));
      pos = (pos+1)%2;
    }else{
      ll ld1 = d.leader(i - 1);
      ll ld2 = d.leader(i);
      ll ld = d.merge(i - 1, i);
      tasu_a[ld] = tasu_a[ld1] + tasu_a[ld2];
      tasu_b[ld] = tasu_b[ld1] + tasu_b[ld2];
      l[ld] = min(l[ld1], l[ld2]);
      r[ld] = max(r[ld1], r[ld2]);
      selected[ld] = pos;
      d.merge(ld1, ld2);
    }
  }
  ll restId = d.leader(N);
  que.push(make_tuple(tasu_b[restId] - tasu_a[restId], restId, l[restId], r[restId], selected[restId]));
  ans += tasu_a[d.leader(N)];
  
  while(!que.empty()){
    auto [dd, idx, tl, tr, sel] = que.top();
    //cout << dd << " " << idx << " " << tl << " " << tr << " " << sel << " " << chg << endl;
    que.pop();
    if(chg <= K) continue; //flip不要
    if(tl != l[idx] || tr != r[idx]) continue;
    ll chgplus = 0;
    ll ld1 = d.leader(max(0LL, tl - 1));
    ll ld2 = d.leader(min(N, tr + 1));
    if(selected[idx] != selected[ld1]) chgplus++;
    if(selected[idx] != selected[ld2]) chgplus++;
    if(chgplus <= 0) continue; //入らないはず
    if(chg % 2 == K % 2 && chgplus == 1) continue; //もう1回余分にflipが必要になるのでやらない
    ans += dd;
    ll nextasu_a = tasu_b[idx], nextasu_b = tasu_a[idx];
    ll nexld = idx;
    if(selected[idx] != selected[ld1]){
      nextasu_a += tasu_a[ld1];
      nextasu_b += tasu_b[ld1];
      nexld = d.merge(idx, ld1);
      l[nexld] = min(l[idx], l[ld1]);
      r[nexld] = max(r[idx], r[ld1]);
    }
    if(selected[idx] != selected[ld2]){
      nextasu_a += tasu_a[ld2];
      nextasu_b += tasu_b[ld2];
      nexld = d.merge(nexld, ld2);
      l[nexld] = min(l[nexld], l[ld2]);
      r[nexld] = max(r[nexld], r[ld2]);
    }
    selected[nexld] = (selected[idx] + 1) % 2;
    tasu_b[nexld] = nextasu_b;
    tasu_a[nexld] = nextasu_a;
    que.push(make_tuple(tasu_b[nexld] - tasu_a[nexld], nexld, l[nexld], r[nexld], selected[nexld]));
    chg -= chgplus;
  }
  cout << ans << endl;
  return 0;
}
0