結果
| 問題 | No.3801 Split Pairs |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-13 23:46:55 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 166 ms / 2,000 ms |
| + 487µs | |
| コード長 | 4,861 bytes |
| 記録 | |
| コンパイル時間 | 2,156 ms |
| コンパイル使用メモリ | 228,444 KB |
| 実行使用メモリ | 16,640 KB |
| 最終ジャッジ日時 | 2026-11-13 23:47:04 |
| 合計ジャッジ時間 | 6,363 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 35 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
template<typename T=long long>
struct IntervalSet{ //区間をsetで管理するテク~
T len;
set<pair<T,T>> S;
IntervalSet():len(0){}
T add(T l,T r){ //[l,r]を追加.
auto memolen = len;
assert(l <= r);
auto itr = S.lower_bound({l,-1});
if(itr != S.begin()) itr--;
vector<pair<T,T>> Era;
while(itr != S.end()){
auto [L,R] = *itr; itr++;
if(R+1 < l) continue;
if(r+1 < L) break;
len -= R-L+1,Era.push_back({L,R});
l = min(l,L),r = max(r,R);
}
for(auto e : Era) S.erase(e);
len += r-l+1,S.insert({l,r});
return len-memolen; //追加した区間長.
}
T era(T l,T r){ //[l,r]を削除.
auto memolen = len;
assert(l <= r);
auto itr = S.lower_bound({l,-1});
if(itr != S.begin()) itr--;
vector<pair<T,T>> Era,Add;
while(itr != S.end()){
auto [L,R] = *itr; itr++;
if(R < l) continue;
if(r < L) break;
len -= R-L+1,Era.push_back({L,R});
if(L < l) Add.push_back({L,l-1});
if(r < R) Add.push_back({r+1,R});
}
for(auto e : Era) S.erase(e);
for(auto a : Add) S.insert(a);
for(auto [L,R] : Add) len += R-L+1;
return memolen-len; //削除した区間長.
}
vector<pair<T,T>> add2(T l,T r){ //[l,r]を追加 追加した区間を返す.
assert(l <= r);
auto itr = S.lower_bound({l,-1});
if(itr != S.begin()) itr--;
vector<pair<T,T>> Era,ret;
long long al = l,ar = r;
while(itr != S.end()){
auto [L,R] = *itr; itr++;
if(R+1 < l) continue;
if(r+1 < L) break;
len -= R-L+1,Era.push_back({L,R});
if(al < L) ret.push_back({al,L-1});
l = min(l,L),r = max(r,R),al = R+1;
}
for(auto e : Era) S.erase(e);
len += r-l+1,S.insert({l,r});
if(al <= ar) ret.push_back({al,ar});
return ret;
}
vector<pair<T,T>> era2(T l,T r){ //[l,r]を削除 削除した区間を返す.
assert(l <= r);
auto itr = S.lower_bound({l,-1});
if(itr != S.begin()) itr--;
vector<pair<T,T>> Era,Add,ret;
while(itr != S.end()){
auto [L,R] = *itr; itr++;
if(R < l) continue;
if(r < L) break;
len -= R-L+1,Era.push_back({L,R});
T dl = L,dr = R;
if(L < l) Add.push_back({L,l-1}),dl = l;
if(r < R) Add.push_back({r+1,R}),dr = r;
ret.push_back({dl,dr});
}
for(auto e : Era) S.erase(e);
for(auto a : Add) S.insert(a);
for(auto [L,R] : Add) len += R-L+1;
return ret;
}
pair<vector<pair<T,T>>,vector<pair<T,T>>> add3(T l,T r){ //[l,r]を追加 変わった区間を返す.
assert(l <= r);
auto itr = S.lower_bound({l,-1});
if(itr != S.begin()) itr--;
vector<pair<T,T>> Era;
while(itr != S.end()){
auto [L,R] = *itr; itr++;
if(R+1 < l) continue;
if(r+1 < L) break;
len -= R-L+1;
Era.push_back({L,R});
l = min(l,L),r = max(r,R);
}
for(auto e : Era) S.erase(e);
len += r-l+1,S.insert({l,r});
return {{{l,r}},Era};
}
pair<vector<pair<T,T>>,vector<pair<T,T>>> era3(T l,T r){ //[l,r]を削除 変わった区間を返す.
assert(l <= r);
auto itr = S.lower_bound({l,-1});
if(itr != S.begin()) itr--;
vector<pair<T,T>> Era,Add;
while(itr != S.end()){
auto [L,R] = *itr; itr++;
if(R < l) continue;
if(r < L) break;
len -= R-L+1,Era.push_back({L,R});
if(L < l) Add.push_back({L,l-1});
if(r < R) Add.push_back({r+1,R});
}
for(auto e : Era) S.erase(e);
for(auto a : Add) S.insert(a);
for(auto [L,R] : Add) len += R-L+1;
return {Add,Era};
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N; cin >> N;
vector<int> A(N);
for(auto &a : A) cin >> a;
IntervalSet S;
long long answer = 0;
for(auto a : A){
auto itr = S.S.lower_bound({a+1,-1});
if(itr == S.S.begin()) S.add(a,a);
else{
itr--;
auto [l,r] = *itr;
if(l <= a && a <= r){
S.era(l,r);
long long left = a-l+1,right = r-a+1,len = r-l+1,len2 = len+2-2*min(left,right);
answer += (len+len2)*min(left,right)/2;
S.add(l-1,l-1+right-1),S.add(r+1-left+1,r+1);
}
else S.add(a,a);
}
}
cout << answer << endl;
}