結果
| 問題 |
No.3091 The Little Match Boy
|
| コンテスト | |
| ユーザー |
 yimiya（いみや）
|
| 提出日時 | 2025-04-06 15:48:28 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 69 ms / 2,000 ms |
| コード長 | 13,365 bytes |
| コンパイル時間 | 4,103 ms |
| コンパイル使用メモリ | 291,456 KB |
| 実行使用メモリ | 8,192 KB |
| 最終ジャッジ日時 | 2025-04-06 15:48:36 |
| 合計ジャッジ時間 | 6,546 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 62 |
ソースコード
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <chrono>
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define rep(i,n) for (ll i = 0;i < (ll)(n);i++)
#define Yes cout << "Yes" << "\n"// YESの短縮
#define No cout << "No" << "\n"// NOの短縮
#define rtr0 return(0)//return(0)の短縮
#define gyakugen(x) modpow(x,mod - 2,mod);
#define agyakugen(x) modpow(x,amod - 2,amod);
using namespace std;
//using namespace ranges;
using ll = long long;//63bit型整数型
using ld = long double;//doubleよりも長い値を保存できるもの
using ull = unsigned long long;//符号がない64bit型整数
ll mod = 998244353;
ll amod = 1000000007;
ll MINF = -5000000000000000000;
ll INF = 5000000000000000000;
ll inf = 5000000000;
ll minf = -5000000000;
ll BAD = -1;
vector<ll>tate = {0,-1,0,1};//グリッド上の全探索時の四方向の上下のチェック
vector<ll>yoko = {1,0,-1,0};//グリッド上の全探索時の四方向の右左のチェック
vector<ll>eightx = {0,-1,-1,-1,0,1,1,1};//グリッド上の全探索時の八方向の上下のチェック
vector<ll>eighty = {1,1,0,-1,-1,-1,0,1};//グリッド上の全探索時の八方向の右左のチェック
vector<ll>hexsax = {0,1,1,0,-1,-1};
vector<ll>hexsay = {1,1,0,-1,-1,0};
//返り値は素数のリスト。
vector < bool > isprime;
vector < ll > Era(int n){//書き方 vector<ll>[] = Era(x); とやるとxまでの素数が出てくる。
isprime.resize(n, true);
vector < ll > res;
isprime[0] = false;
isprime[1] = false;
for(ll i = 2; i < n; ++i) isprime[i] = true;
for(ll i = 2; i < n; ++i) {
if(isprime[i]) {
res.push_back(i);
for(ll j = i * 2; j < n; j += i) isprime[j] = false;
}
}
return res;
}
// 素数判定 21~35
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
long long npow(long long a, long long n){
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a;
a = a * a;
n >>= 1;
}
return res;
}
// モッドを使った累乗
template<class T>
struct dijkstra{
public:
vector<vector<pair<T,T>>>graph;
vector<T>ans;
priority_queue<pair<T,T>,vector<pair<T,T>>,greater<pair<T,T>>>pq;
void do_dijkstra(T start){//頂点xからダイクストラを行う
pq.push({0,start});
ans[start] = 0;
while(true){
if(pq.empty())break;
T cost = pq.top().first;
T vertex = pq.top().second;
pq.pop();
for(T i = 0;i<graph[vertex].size();i++){
T nextvertex = graph[vertex][i].first;
T nextcost = graph[vertex][i].second + cost;
if(ans[nextvertex] > nextcost){
ans[nextvertex] = nextcost;
pq.push({nextcost,nextvertex});
}
}
}
}
void make_indirectedgraph(T u,T v,T cost){//無向辺のグラフ作成
graph[u].push_back({v,cost});
graph[v].push_back({u,cost});
}
void make_directedgraph(T u,T v,T cost){//有向辺のグラフ作成
graph[u].push_back({v,cost});
}
T output(T end){//答えを出す
return ans[end];
}
void reset(T N){//リセット
graph.clear();
ans.clear();
for(ll i = 0;i<N;i++){
graph.push_back({vector<pair<T,T>>(0)});
ans.push_back(INF);
}
}
};
template<class T>
struct unionfind {
public:
vector<T> parent, rank;
void reset(T N) { // 初期化
parent.resize(N);
rank.assign(N, 1); // 各集合のサイズを 1 にする
for (T i = 0; i < N; i++) parent[i] = i;
}
T leader(T x) { // 経路圧縮による親の取得
if (parent[x] == x) return x;
return parent[x] = leader(parent[x]); // 経路圧縮
}
void marge(T x, T y) { // ランクによるマージ
T a = leader(x), b = leader(y);
if(a!=b){
if (rank[a] < rank[b]) swap(a, b);
parent[b] = a;
rank[a] += rank[b]; // サイズを更新
}
}
bool same(T x, T y) { // 同じ集合か判定
return leader(x) == leader(y);
}
T size(T x) { // 集合のサイズを取得
return rank[leader(x)];
}
void check(T N) { // デバッグ用: 親の確認
for (T i = 0; i < N; i++) cout << parent[i] << " ";
cout << "\n";
}
};
//セグ木
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n(int(v.size())){
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do{
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
}while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do{
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
}while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
};
//遅延セグ木
template <class S,S (*op)(S, S),S (*e)(),class F,S (*mapping)(F, S),F (*composition)(F, F),F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push(r >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
//遅延セグ木のベース
using lazyS = ll;
using lazyF = ll;//型
lazyS e(){ return 0;}//範囲外などを起こしてしまったときの返り値
lazyS op(lazyS a, lazyS b){ return a+b; }//操作したいこと
lazyS mapping(lazyF f, lazyS x){ return x+f; }//下まで伝播させたいこと
lazyF composition(lazyF f, lazyF g){ return g+f; }//まとめてやった場合おこしたいこと
lazyF id(){ return 0; }//遅延セグ木のベース
int main(){
//B以上は基本詳細を書いておくと便利 A ＝ ooの値とか 見直す時に便利
// この問題の本質
ll N,M;
cin >> N >> M;
vector<ll>A(N);
for(ll i = 0;i<N;i++)A[i] = i;
set<pair<ll,ll>>X;
for(ll i = 0;i<M;i++){
ll a;
cin >> a;
a--;
ll x = A[a];
ll y = A[a+1];
X.insert({min(x,y),max(x,y)});
swap(A[a],A[a+1]);
}
cout << X.size() << "\n";
}