結果

問題 No.3058 Deque and Brackets
コンテスト
ユーザー pockyny
提出日時 2025-07-12 05:15:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 63 ms / 2,000 ms
コード長 2,647 bytes
コンパイル時間 1,031 ms
コンパイル使用メモリ 77,696 KB
実行使用メモリ 7,808 KB
最終ジャッジ日時 2025-07-12 05:16:00
合計ジャッジ時間 3,864 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <cassert>

using namespace std;
typedef long long ll;
char c[200010];
ll l[200010],r[200010],inf = 1000000000000000;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,n; cin >> n;
    for(i=0;i<2*n;i++) cin >> c[i] >> l[i] >> r[i];
    ll ans = 0;
    // le := (で左に来たやつ
    // ri := )で右に来たやつ
    ll le = 0,ri = 0;
    // quel := )で左に来てるやつ
    // quer := (で右に来てるやつ
    priority_queue<ll,vector<ll>,greater<ll>> quel,quer;
    for(i=2*n - 1;i>=0;i--){
        if(c[i]=='('){
            if(l[i]>=r[i]){
                ans += l[i];
                le++;
            }else{
                ans += l[i];
                ll d = r[i] - l[i];
                if(quer.size()<ri){
                    ans += d;
                    quer.push(d);
                }else{
                    // querと交換 or quelを一個右側に持っていく
                    ll valr = quer.size() ? quer.top() : inf;
                    ll vall = quel.size() ? quel.top() : inf;
                    if(vall<valr && vall<d){
                        ans += d - vall;
                        quel.pop(); quer.push(d); ri++;
                    }else if(valr<=vall && valr<d){
                        ans += d - valr;
                        quer.pop(); quer.push(d); le++;
                    }else{
                        le++;
                    }
                }
            }
        }else{
            if(l[i]<=r[i]){
                ans += r[i];
                ri++;
            }else{
                ans += r[i];
                ll d = l[i] - r[i];
                if(quel.size()<le){
                    quel.push(d);
                    ans += d;
                }else{
                    // quelと交換 or querを一個左側に持っていく
                    ll valr = quer.size() ? quer.top() : inf;
                    ll vall = quel.size() ? quel.top() : inf;
                    if(vall<valr && vall<d){
                        ans += d - vall;
                        quel.pop(); quel.push(d); ri++;
                    }else if(valr<=vall && valr<d){
                        ans += d - valr;
                        quer.pop(); quel.push(d); le++;
                    }else{
                        ri++;
                    }
                }
            }
        }
        assert(quel.size()<=le);
        assert(quer.size()<=ri);
        // cout << le << " " << ri << " " << quel.size() << " " << quer.size() << " " << (le + ri + quel.size() + quer.size()) << "\n";
    }
    cout << ans << "\n";
}
0