結果
問題 |
No.3164 [Chery 7th Tune B] La vie en rose
|
ユーザー |
|
提出日時 | 2025-05-30 21:33:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 1,550 bytes |
コンパイル時間 | 2,723 ms |
コンパイル使用メモリ | 204,548 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2025-05-30 21:33:38 |
合計ジャッジ時間 | 10,165 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; class UnionFind{ private: vector<long long> par,siz; public: UnionFind(long long N,vector<long long> A){ par.resize(N,-1); siz = A; } long long root(long long x){ //連結成分の代表頂点を返す. if(par.at(x) == -1) return x; else return par.at(x) = root(par.at(x)); } bool unite(long long u, long long v){ //u,vを連結する 連結してた->false,した->trueを返す. u = root(u),v = root(v); if(u == v) return false; if(siz.at(u) < siz.at(v)) swap(u,v); //Union by size. par.at(v) = u; siz.at(u) += siz.at(v); return true; } bool issame(long long u, long long v){ //同じ連結成分ならtrue. if(root(u) == root(v)) return true; else return false; } long long size(long long pos){return siz.at(root(pos));} //posの連結成分の大きさを返す. }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); long long N; cin >> N; vector<long long> A(N+2); for(long long i=1; i<=N; i++) cin >> A.at(i); UnionFind Z(N+2,A); for(long long i=0; i<N+1; i++) if(A.at(i) > 0 && A.at(i+1) > 0) Z.unite(i,i+1); long long Q; cin >> Q; while(Q--){ long long p,b; cin >> p >> b; long long add = b-A.at(p); long long l = 0,r = 0; l = Z.size(p-1); r = Z.size(p+1); if(Z.issame(p-1,p+1)) r = 0; cout << max(b,l+r+add) << "\n"; } }