結果

問題 No.1014 competitive fighting
ユーザー Y17
提出日時 2020-03-20 23:42:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 649 ms / 2,000 ms
コード長 3,565 bytes
コンパイル時間 2,279 ms
コンパイル使用メモリ 189,756 KB
実行使用メモリ 191,628 KB
最終ジャッジ日時 2024-07-07 12:56:28
合計ジャッジ時間 22,182 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

vector<vector<int>> graph(500010);

vector<int> seg;
using UnWeightedGraph = vector< vector< int > >;

int num[500010];
int n;
template< typename G >
struct StronglyConnectedComponents {
  const G &g;
  UnWeightedGraph gg, rg;
  vector< int > comp, order, used;

  StronglyConnectedComponents(G &g) : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), used(g.size()) {
    for(int i = 0; i < g.size(); i++) {
      for(auto e : g[i]) {
        gg[i].emplace_back((int) e);
        rg[(int) e].emplace_back(i);
      }
    }
  }

  int operator[](int k) {
    return comp[k];
  }

  void dfs(int idx) {
    if(used[idx]) return;
    used[idx] = true;
    for(int to : gg[idx]) dfs(to);
    order.push_back(idx);
  }

  void rdfs(int idx, int cnt) {
    if(comp[idx] != -1) return;
    comp[idx] = cnt;
    for(int to : rg[idx]) rdfs(to, cnt);
  }

  void build(UnWeightedGraph &t) {
    for(int i = 0; i < gg.size(); i++) dfs(i);
    reverse(begin(order), end(order));
    int ptr = 0;
    for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++;

    t.resize(ptr);
    for(int i = 0; i < g.size(); i++) {
      for(auto &to : g[i]) {
        int x = comp[i], y = comp[to];
        if(x == y) continue;
        t[x].push_back(y);
      }
    }
  }
};

int size;
int init(int n){
	int sz = n;
	size = 1; while(size < sz) size *= 2;
	int si = n;
	seg.resize(2*size);
	for(int i = 0;i < size;i++){
		seg[i+size-1] = si;
		if(i < n) graph[si].push_back(i);
		si++;
	}

	for(int i = size-2;i >= 0;i--){
		seg[i] = si;
		graph[si].push_back(seg[i*2+1]);
		graph[si].push_back(seg[i*2+2]);
		si++;
	}
	return si;
}

void add_edge(int a, int b, int num, int k=0, int l=0, int r=size){
	if(r <= a || b <= l) return;
	if(a <= l && r <= b) {
		graph[num].push_back(seg[k]);
		return;
	}

	add_edge(a, b, num, 2*k+1, l, (l+r)/2); 
	add_edge(a, b, num, 2*k+2, (l+r)/2, r); 
}

vector<vector<int>> ngraph;
int cnt[1000010];

int memo[1000010];

int dp(int idx){
	if(cnt[idx] > 2){
		return LLONG_MAX;
	}
	if(memo[idx] != -1) return memo[idx];

	int ans = num[idx];
	for(int i = 0;i < ngraph[idx].size();i++){
		int tmp = dp(ngraph[idx][i]);
		if(tmp == LLONG_MAX) return memo[idx] = tmp;
		ans = max(ans, tmp+num[idx]);
	}
	return memo[idx] = ans;
}

signed main(){
	cin >> n;

	vector<pair<int, pair<int, int>>> p, konbo;
	vector<int> aa;

	int all_n = init(n);

	for(int i = 0;i < n;i++){
		int a, b, c;
		cin >> a >> b >> c;
		p.push_back({a, {b, c}});
		konbo.push_back({a, {b, c}});
		aa.push_back(a);
	}

	sort(p.begin(), p.end());
	sort(aa.begin(), aa.end());

	for(int i = 0;i < n;i++){
		int idx = upper_bound(aa.begin(), aa.end(), p[i].second.first-p[i].second.second) - aa.begin();
		if(idx <= i){
			add_edge(0, idx, i);
		}else{
			add_edge(0, i, i);
			add_edge(i+1, idx, i);
		}
	}

	StronglyConnectedComponents<vector<vector<int>>> kyo(graph);
	kyo.build(ngraph);

	for(int i = 0;i < all_n;i++){
		cnt[kyo[i]]++;
	}

	for(int i = 0;i < n;i++){
		int idx = lower_bound(p.begin(), p.end(), konbo[i]) - p.begin();
		num[kyo[idx]] = p[idx].second.first;
	}

	memset(memo, -1, sizeof(memo));

	for(int i = 0;i < n;i++){
		int idx = lower_bound(p.begin(), p.end(), konbo[i]) - p.begin();
		int ans = dp(kyo[idx]);
		if(ans == LLONG_MAX){
			cout << "BAN" << endl;
		}else{
			cout << ans << endl;
		}
	}
	
	return 0;
}
0