結果

問題 No.1170 Never Want to Walk
ユーザー SSRSSSRS
提出日時 2020-08-14 21:43:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,107 ms / 2,000 ms
コード長 2,737 bytes
コンパイル時間 2,046 ms
コンパイル使用メモリ 189,428 KB
実行使用メモリ 188,136 KB
最終ジャッジ日時 2024-10-10 14:47:31
合計ジャッジ時間 14,660 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct range_edges{
	int N;
	int V;
	vector<vector<pair<T, int>>> E;
	range_edges(int n){
		N = 1;
		while (N < n){
			N *= 2;
		}
		V = N * 5 - 2;
		E = vector<vector<pair<T, int>>>(V);
		for (int i = 0; i < N - 1; i++){
			E[i].emplace_back(0, i * 2 + 1);
			E[i].emplace_back(0, i * 2 + 2);
			E[i * 2 + N * 2].emplace_back(0, i + N * 2 - 1);
			E[i * 2 + N * 2 + 1].emplace_back(0, i + N * 2 - 1);
		}
		for (int i = 0; i < N; i++){
			E[N - 1 + i].emplace_back(0, N * 4 - 2 + i);
			E[N * 4 - 2 + i].emplace_back(0, N * 3 - 2 + i);
		}
	}
	void add_edge_from(int L, int R, int v, int i, int l, int r){
		if (R <= l || r <= L){
			return;
		} else if (L <= l && r <= R){
			E[i + N * 2 - 1].emplace_back(0, v);
		} else {
			int m = (l + r) / 2;
			add_edge_from(L, R, v, i * 2 + 1, l, m);
			add_edge_from(L, R, v, i * 2 + 2, m, r);
		}
	}
	void add_edge_from(int L, int R, int v){
		add_edge_from(L, R, v, 0, 0, N);
	}
	void add_edge_to(int L, int R, int v, int i, int l, int r){
		if (R <= l || r <= L){
			return;
		} else if (L <= l && r <= R){
			E[v].emplace_back(0, i);
		} else {
			int m = (l + r) / 2;
			add_edge_to(L, R, v, i * 2 + 1, l, m);
			add_edge_to(L, R, v, i * 2 + 2, m, r);
		}
	}
	void add_edge_to(int L, int R, int v){
		add_edge_to(L, R, v, 0, 0, N);
	}
	void add_edge(int L1, int R1, int L2, int R2, T cost){
		E.emplace_back();
		E.emplace_back();
		V += 2;
		add_edge_from(L1, R1, V - 2);
		add_edge_to(L2, R2, V - 1);
		E[V - 2].emplace_back(cost, V - 1);
	}
	void debug(){
		for (int i = 0; i < V; i++){
			cout << i << ":";
			for (auto P : E[i]){
				cout << " (" << P.first << "," << P.second << ")";
			}
			cout << endl;
		}
	}
};
int main(){
  int N, A, B;
  cin >> N >> A >> B;
  vector<int> x(N);
  for (int i = 0; i < N; i++){
    cin >> x[i];
  }
  range_edges<int> G(N);
  for (int i = 0; i < N; i++){
    int L = lower_bound(x.begin(), x.end(), x[i] - B) - x.begin();
    int R = upper_bound(x.begin(), x.end(), x[i] - A) - x.begin();
    G.add_edge(L, R, i, i + 1, 1);
    G.add_edge(i, i + 1, L, R, 1);
  }
  vector<int> c(G.V, -1);
  int cnt = 0;
  for (int i = G.N * 4 - 2; i < G.N * 4 - 2 + N; i++){
    if (c[i] == -1){
      c[i] = cnt;
      queue<int> Q;
      Q.push(i);
      while (!Q.empty()){
        int v = Q.front();
        Q.pop();
        for (auto P : G.E[v]){
          int w = P.second;
          if (c[w] == -1){
            c[w] = cnt;
            Q.push(w);
          }
        }
      }
      cnt++;
    }
  }
  map<int, int> mp;
  for (int i = G.N * 4 - 2; i < G.N * 4 - 2 + N; i++){
    mp[c[i]]++;
  }
  for (int i = G.N * 4 - 2; i < G.N * 4 - 2 + N; i++){
    cout << mp[c[i]] << endl;
  }
}
0