結果

問題 No.2821 A[i] ← 2A[j] - A[i]
コンテスト
ユーザー rotti_coder
提出日時 2024-07-26 22:05:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,025 bytes
コンパイル時間 1,219 ms
コンパイル使用メモリ 101,052 KB
最終ジャッジ日時 2025-02-23 18:39:44
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 33
権限があれば一括ダウンロードができます

ソースコード

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