#966021 (C++17(clang)) No.1170 Never Want to Walk

提出ソース

結果

問題	No.1170 Never Want to Walk
ユーザー	00 Sakuda
提出日時	2024-03-30 12:22:50
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	AC
実行時間	450 ms / 2,000 ms
コード長	8,715 bytes
コンパイル時間	3,856 ms
コンパイル使用メモリ	169,168 KB
実行使用メモリ	15,744 KB
最終ジャッジ日時	2024-03-30 12:23:04
合計ジャッジ時間	12,780 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,676 KB
testcase_01	AC	1 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	2 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	1 ms 6,676 KB
testcase_07	AC	1 ms 6,676 KB
testcase_08	AC	2 ms 6,676 KB
testcase_09	AC	1 ms 6,676 KB
testcase_10	AC	2 ms 6,676 KB
testcase_11	AC	2 ms 6,676 KB
testcase_12	AC	3 ms 6,676 KB
testcase_13	AC	4 ms 6,676 KB
testcase_14	AC	3 ms 6,676 KB
testcase_15	AC	3 ms 6,676 KB
testcase_16	AC	3 ms 6,676 KB
testcase_17	AC	4 ms 6,676 KB
testcase_18	AC	3 ms 6,676 KB
testcase_19	AC	4 ms 6,676 KB
testcase_20	AC	3 ms 6,676 KB
testcase_21	AC	4 ms 6,676 KB
testcase_22	AC	3 ms 6,676 KB
testcase_23	AC	3 ms 6,676 KB
testcase_24	AC	4 ms 6,676 KB
testcase_25	AC	3 ms 6,676 KB
testcase_26	AC	4 ms 6,676 KB
testcase_27	AC	418 ms 15,232 KB
testcase_28	AC	413 ms 15,104 KB
testcase_29	AC	447 ms 15,488 KB
testcase_30	AC	425 ms 15,488 KB
testcase_31	AC	415 ms 15,104 KB
testcase_32	AC	434 ms 15,232 KB
testcase_33	AC	412 ms 15,104 KB
testcase_34	AC	427 ms 15,488 KB
testcase_35	AC	444 ms 15,488 KB
testcase_36	AC	416 ms 15,104 KB
testcase_37	AC	416 ms 15,232 KB
testcase_38	AC	450 ms 15,744 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <iomanip>
using namespace std;
using ll = long long;
using VVI = vector<vector<int>>;
using VVL = vector<vector<ll>>;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
using VC = vector<char>;
using VP = vector<pair<int, int>>;
using Graph0 = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define drep(i, a, b) for (int i = (int)(a);i >= (int)(b);i--)
#define urep(i, a, b) for (int i = (int)(a);i <= (int)(b);i++)
#define lrep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ldrep(i, a, b) for (ll i = (ll)(a);i >= (ll)(b);i--)
#define lurep(i, a, b) for (ll i = (ll)(a);i <= (ll)(b);i++)
#define arep(i, v) for (auto i : v)
#define all(a) (a).begin(), (a).end()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define eyes cout << "Yes" << endl;exit(0);
#define eno cout << "No" << endl;exit(0);
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b; 
    return true;
  }
  return false;
}
template<typename T>
void excout(T A) {
  cout << A << endl;
  exit(0);
}
constexpr long long INF = (1LL << 60); // INFにちゅういい！

// 辺の情報
struct Edge
{
  // 行先
  int to;

  // コスト
  int cost;
};

using Graph = std::vector<std::vector<Edge>>;

// { distance, from }
using Pair = std::pair<long long, int>;

// ダイクストラ法 (1.1 基本実装)
// distances は頂点数と同じサイズ, 全要素 INF で初期化しておく
void Dijkstra(const Graph& graph, std::vector<long long>& distances, int startIndex)
{
  // 「現時点での最短距離, 頂点」の順に取り出す priority_queue
  // デフォルトの priority_queue は降順に取り出すため std::greater を使う
  std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> q;
  q.emplace((distances[startIndex] = 0), startIndex);

  while (!q.empty())
  {
    const long long distance = q.top().first;
    const int from = q.top().second;
    q.pop();

    // 最短距離でなければ処理しない
    if (distances[from] < distance)
    {
      continue;
    }

    // 現在の頂点からの各辺について
    for (const auto& edge : graph[from])
    {
      // to までの新しい距離
      const long long d = (distances[from] + edge.cost);

      // d が現在の記録より小さければ更新
      if (d < distances[edge.to])
      {
        q.emplace((distances[edge.to] = d), edge.to);
      }
    }
  }
}
template<typename T>
T MODS(T a, T mods) {
  return ((((((a + mods) % mods) + mods) % mods)));
}
//combination 列挙用 --int ver
VVI comb(int n, int r) {
  VVI v(n + 1, VI (n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}
vector<pair<long long, long long> > prime_factorize(long long N) {
    // 答えを表す可変長配列
    vector<pair<long long, long long> > res;

    // √N まで試し割っていく
    for (long long p = 2; p * p <= N; ++p) {
        // N が p で割り切れないならばスキップ
        if (N % p != 0) {
            continue;
        }

        // N の素因数 p に対する指数を求める
        int e = 0;
        while (N % p == 0) {
            // 指数を 1 増やす
            ++e;

            // N を p で割る
            N /= p;
        }

        // 答えに追加
        res.emplace_back(p, e);
    }

    // 素数が最後に残ることがありうる
    if (N != 1) {
        res.emplace_back(N, 1);
    }
    return res;
}
using UNION_TYPE = int;
struct UnionFind {
    vector<UNION_TYPE> par, siz;
    UnionFind(UNION_TYPE n) : par(n, -1), siz(n, 1) {}
    UNION_TYPE root(UNION_TYPE x) {
        if (par[x] == -1) return x;
        else return par[x] = root(par[x]);
    }
    bool issame(UNION_TYPE x, UNION_TYPE y) {
        return root(x) == root(y);
    }
    bool unite(UNION_TYPE x, UNION_TYPE y) {
        x = root(x);y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        par[y] = x;
        siz[x] += siz[y];
        return true;
    }
    UNION_TYPE size(UNION_TYPE x) {
        return siz[root(x)];
    }
};
//mod func の型に注意！！！
//Union Find はUNION_TYPE で型変可能！
//
VI topo_sort(Graph0& G) {
  int N = G.size();
  VI IND(N, 0);
  rep(v, N) {
    arep(nv, G[v]) {
      IND[nv]++;
    }
  }
  queue<int> que;
  rep(v, N) {
    if (IND[v] == 0) {
      que.push(v);
    }
  }
  VI ANS;
  while (!que.empty()) {
    int v = que.front();
    ANS.push_back(v);
    que.pop();
    arep(nv, G[v]) {
      IND[nv]--;
      if (IND[nv] == 0) {
        que.push(nv);
      }
    }
  }
  return ANS;
}
void ADD(int a, int b, Graph0& G) {
  G[a].push_back(b);
  G[b].push_back(a);
}
VP near(int i, int j, int H, int W) {
  VP ans;
  VP cand = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}};
  arep(v, cand) {
    if (v.first < 0 or v.first >= H) continue;
    if (v.second < 0 or v.second >= W) continue;
    ans.push_back(v);
  }
  return ans;
}
int cast(int i, int j, int H, int W) {
  return ((W * i) + j);
}
ll pows(ll x, ll n, ll mod) {
    if (!n) return 1;
    x %= mod;
    ll r = pows(x, n / 2, mod);
    (r *= r) %= mod;
    if (n % 2) (r *=x) %= mod;
    return r;
}
struct COMB_MOD {
  ll mod;
  int MAX;
  VL fac, finv, inv;
  COMB_MOD(int max, ll m) {
    fac.assign(max, 0);
    finv.assign(max, 0);
    inv.assign(max, 0);
    mod = m;
    MAX = max;
  }
  void solve() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;

        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
    
  }
  ll comb(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
  }
};

struct LCA {
    vector<vector<int>> parent;  // parent[k][u]:= u の 2^k 先の親
    vector<int> dist;            // root からの距離
    LCA(const Graph0 &G, int root = 0) { init(G, root); }

    // 初期化
    void init(const Graph0 &G, int root = 0) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        parent.assign(K, vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    // 根からの距離と1つ先の頂点を求める
    void dfs(const Graph0 &G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e != p) dfs(G, e, v, d + 1);
        }
    }

    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v);  // u の方が深いとする
        int K = parent.size();
        // LCA までの距離を同じにする
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        // 二分探索で LCA を求める
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
    int get_dist(int u, int v) { return dist[u] + dist[v] - 2 * dist[query(u, v)]; }
};
int main(void) {
    int N, A, B;cin >> N >> A >> B;
    map<int, int> tos;

    VI X(N);
    rep(i, N) {
      cin >> X[i];
      tos[X[i]] = i;

    }
    UnionFind uf(N);
	VI S(N, 0);
	rep(i, N) {
		auto itr = lower_bound(all(X), X[i] - B);
		auto it = upper_bound(all(X), X[i] - A);
		if (it == X.begin() or *itr >= X[i]) continue;
		int l = itr - X.begin();
		it--;int r = it - X.begin();
		if (*it < *itr) continue;
		uf.unite(i, l);uf.unite(i, r);
		S[l]++;
		//cout << i << " " << l << " " <<r << endl;
		if (r < N) S[r]--;
	}
	int s = 0;
	rep(i, N) {
		s += S[i];
		if (s > 0 and i != N - 1) uf.unite(i, i + 1);
	}
	rep(i, N) cout << uf.size(i) << endl;
}

yukicoder

結果

テストケース

ソースコード