結果

問題 No.1170 Never Want to Walk
ユーザー SSRSSSRS
提出日時 2020-08-14 21:43:19
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,001 ms / 2,000 ms
コード長 2,737 bytes
コンパイル時間 2,140 ms
コンパイル使用メモリ 184,068 KB
実行使用メモリ 186,704 KB
最終ジャッジ日時 2024-04-18 21:21:05
合計ジャッジ時間 13,952 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 4 ms
5,376 KB
testcase_13 AC 4 ms
5,376 KB
testcase_14 AC 4 ms
5,376 KB
testcase_15 AC 5 ms
5,376 KB
testcase_16 AC 4 ms
5,376 KB
testcase_17 AC 4 ms
5,376 KB
testcase_18 AC 5 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 4 ms
5,376 KB
testcase_21 AC 4 ms
5,376 KB
testcase_22 AC 5 ms
5,376 KB
testcase_23 AC 4 ms
5,376 KB
testcase_24 AC 5 ms
5,376 KB
testcase_25 AC 4 ms
5,376 KB
testcase_26 AC 5 ms
5,376 KB
testcase_27 AC 666 ms
130,748 KB
testcase_28 AC 659 ms
130,356 KB
testcase_29 AC 681 ms
130,504 KB
testcase_30 AC 688 ms
131,400 KB
testcase_31 AC 686 ms
129,972 KB
testcase_32 AC 943 ms
183,996 KB
testcase_33 AC 1,001 ms
183,600 KB
testcase_34 AC 919 ms
186,704 KB
testcase_35 AC 939 ms
186,568 KB
testcase_36 AC 976 ms
183,092 KB
testcase_37 AC 854 ms
160,952 KB
testcase_38 AC 870 ms
165,204 KB
権限があれば一括ダウンロードができます

ソースコード

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