結果

問題 No.2821 A[i] ← 2A[j] - A[i]
ユーザー rotti_coderrotti_coder
提出日時 2024-07-26 22:05:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,025 bytes
コンパイル時間 1,494 ms
コンパイル使用メモリ 107,156 KB
実行使用メモリ 24,448 KB
最終ジャッジ日時 2024-07-26 22:05:27
合計ジャッジ時間 9,556 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

//このコンテスト難しいですよぅ（泣）
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<long long>A(n);
  for(int i=0;i<n;i++)cin >> A[i];
  priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>prq_min;
  priority_queue<pair<long long,int>>prq_max;
  map<int,long long>dict;

  prq_min.push(make_pair(A[0],1));
  prq_max.push(make_pair(A[0],1));
  dict[1]=A[0];

  cout << 0 << endl;

  long long x=A[0],y=A[0];

  for(int i=1;i<n;i++){
    long long a=A[i];

    //minから
    while(true){
      pair<long long,int>hako=prq_min.top();
      prq_min.pop();
      if(hako.first!=dict[hako.second]){
	prq_min.push(make_pair(dict[hako.second],hako.second));
	continue;
      }
      if(a*2-hako.first>x && a*2-hako.first<=y){
	dict[hako.second]=a*2-hako.first;
	prq_min.push(make_pair(a*2-hako.first,hako.second));
	x=prq_min.top().first;
      }
      else break;
    }

    //max
    while(true){
      pair<long long,int>hako=prq_max.top();
      prq_max.pop();
      if(hako.first!=dict[hako.second]){
	prq_max.push(make_pair(dict[hako.second],hako.second));
	continue;
      }
      if(a*2-hako.first<y && a*2-hako.first>=x){
	dict[hako.second]=a*2-hako.first;
	prq_max.push(make_pair(a*2-hako.first,hako.second));
	y=prq_max.top().first;
      }
      else break;
    }

    vector<pair<long long,long long>>rotti(3);
    rotti[0].second=a;
    rotti[1].second=x*2-a;
    rotti[2].second=y*2-a;
    for(int j=0;j<3;j++){
      if(x<=rotti[j].second && rotti[j].second<=y)rotti[j].first=0;
      else rotti[j].first=min(abs(x-rotti[j].second),abs(y-rotti[j].second));
    }
    sort(rotti.begin(),rotti.end());
    if(rotti[0].second<x)x=rotti[0].second;
    else if(rotti[0].second>y)y=rotti[0].second;
    dict[i+1]=rotti[0].second;
    prq_min.push(make_pair(rotti[0].second,i+1));
    prq_max.push(make_pair(rotti[0].second,i+1));
    cout << y-x << endl;
  }
}
0