Codeforces Round #519 E. Train Hard, Win Easy
考えたこと
- 頑張って問題文を読む
- ペアを組んじゃだめな二人組についてはとりあえず無視する
- i番目の人のスコアは ans[i] = sum(min(a[i]+b[j],b[i]+a[j])) (i!=j) となる
- a[i]+b[j] < b[i]+a[j] ⇔ a[i]-b[i] < a[j]-b[j] となる
- 2人を選んだときにa[i]-b[i]の大小でスコアが2通りのうちのどちらになるか決定できる
- a[i]-b[j]であらかじめソートしておく
- ans[i] = (i番目とj番目の人のチームのスコアの和) + (i番目とk番目の人のチームのスコアの和) (j<i<k) となる
- (i番目とj番目の人のチームのスコアの和) = b[i]*i + sum(a[j])
- (i番目とk番目の人のチームのスコアの和) = a[i]*(n-1-i) + sum(b[j])
- 区間和を高速に求めるには累積和を取っておけばよい
- ペアを組んじゃだめな二人組について考える
- g[i] = {iとペアを組んじゃだめな人の集合} のように隣接リスト的なものを持っておく
- この二人組の数は高々O(m)個なので全部見たとしても計算量的に問題ないはず
- sortが一番重そうでO(nlogn+mlogm)くらいになりそう
集合について比較するときに不等式を書いて同じ集合の要素を片側に寄せるとうまくいくやつ
ソートする前と後のindexの変化だったりで実装をバグらせないのがちょっと大変
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) {is >> x;} return is; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n, m; cin >> n >> m; vector<ll> a(n), b(n), x(m), y(m); REP(i, n) cin >> a[i] >> b[i]; REP(i, m) { cin >> x[i] >> y[i]; x[i]--, y[i]--; } vector<ll> untrans(n), trans(n); vector<PII> vec(n); REP(i, n) vec[i] = {a[i]-b[i], i}; sort(ALL(vec)); REP(i, n) { untrans[i] = vec[i].second; trans[vec[i].second] = i; } vector<ll> na(n), nb(n), nx(m), ny(m); REP(i, n) { na[i] = a[untrans[i]]; nb[i] = b[untrans[i]]; } vector<vector<ll>> g(n); REP(i, m) { nx[i] = trans[x[i]]; ny[i] = trans[y[i]]; g[nx[i]].push_back(ny[i]); g[ny[i]].push_back(nx[i]); } swap(na, a); swap(nb, b); swap(nx, x); swap(ny, y); vector<ll> suma(n), sumb(n); suma[0] = a[0], sumb[0] = b[0]; FOR(i, 1, n) { suma[i] = suma[i-1] + a[i]; sumb[i] = sumb[i-1] + b[i]; } vector<ll> ans(n); REP(i, n) { // [0,i)ならばb[i]+a[j] ll tmp1 = i*b[i] + (i==0?0:suma[i-1]); // (i,n-1]ならばa[i]+b[j] ll tmp2 = (n-1-i)*a[i] + sumb[n-1] - sumb[i]; for(auto j: g[i]) { if(j < i) { tmp1 -= b[i] + a[j]; } else { tmp2 -= a[i] + b[j]; } } ans[untrans[i]] = tmp1 + tmp2; } REP(i, ans.size()) cout << ans[i] << (i==ans.size()-1?'\n':' '); cout << flush; return 0; }