#1078334 (C++23) No.3116 More and more teleporter

提出ソース
結果

問題	No.3116 More and more teleporter
ユーザー	sic2
提出日時	2025-04-20 17:26:29
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	9,705 bytes
コンパイル時間	1,670 ms
コンパイル使用メモリ	133,312 KB
実行使用メモリ	12,800 KB
最終ジャッジ日時	2025-04-20 17:26:36
合計ジャッジ時間	6,266 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 4 WA * 18
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma region HEADER

#include <array>
#include <vector>
#include <string>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <initializer_list>
using namespace std;

// === TYPE & CONST === //
using INT128 = __int128_t;

using INT = long long int;
const INT INF = 1LL << 60LL;

using FLOAT = long double;

using INT2      = std::array<INT, 2>;

using INT3      = std::array<INT, 3>;
using INT4      = std::array<INT, 4>;
using INT5      = std::array<INT, 5>;
using INT6      = std::array<INT, 6>;
using INT7      = std::array<INT, 7>;
using INT8      = std::array<INT, 8>;

using FLOAT2    = std::array<FLOAT, 2>;
using FLOAT3    = std::array<FLOAT, 3>;
using FLOAT4    = std::array<FLOAT, 4>;
using FLOAT5    = std::array<FLOAT, 5>;

// col and row axis 
enum class DIR4 : INT { DOWN, RIGHT, UP, LEFT };
const INT2 dxdy[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };
const INT2 dxdy4[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

// 8 direction 
enum class DIR8 : INT { DOWN, RIGHT, UP, LEFT, DR, UR, UL, DL };
const INT2 dxdy8[8] = { {1,0}, {0,1}, {-1,0}, {0,-1}, {1,1}, {-1,1}, {-1,-1}, {1,-1} };

// 4 direction with diagonal
enum class DIR4D : INT { DR, UR, UL, DL };
const INT2 ppmm[4] = { {1,1}, {-1,1}, {-1,-1}, {1,-1} };

template< typename T > using vector2d = std::vector< std::vector<T> >;
template< typename T > using vector3d = std::vector< vector2d<T> >;
template< typename T > using vector4d = std::vector< vector3d<T> >;

// SCOPE-BREAK Macro
#define SCOPE( STATEMENT ) [&](){ STATEMENT; }();
#define BREAK return;

// [0,N)
#define REP(i, N)        for ( INT i = 0; i < (N); i++ )
#define REP2(i, j, N)    for ( INT i = 0; i < (N); i++ ) REP(j, N)
#define REP3(i, j, k, N) for ( INT i = 0; i < (N); i++ ) REP2(j, k, N)

#define RREP(i, N)      for (INT i = ((N)-1LL); i >= 0; i--)

// FOR
#define FOR(i, str, end)  for ( INT i = str; i < end; i++ )
#define RFOR(i, str, end) for ( INT i = end-1LL; i >= str; i-- )

// Combinated For 
#define COMB_FOR(i, N)                           for( INT i = 0;     i < (N); i++ )
#define COMB_FOR2(i, j, N)    COMB_FOR(i, N)     for( INT j = i+1LL; j < (N); j++ )
#define COMB_FOR3(i, j, k, N) COMB_FOR2(i, j, N) for( INT k = j+1LL; k < (N); k++ )

// Yes or No
void YESNO(bool b){ if(b){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;} }
void yesno(bool b){ if(b){cout<<"yes"<<endl;}else{cout<<"no"<<endl;} }
void YesNo(bool b){ if(b){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;} }
void OneZero(bool b){ if(b){cout<<"1"<<endl;}else{cout<<"0"<<endl;} }

// Range 
#define RANGE(v) begin(v), end(v)

// chmax, chmin 
template< class T > bool chmax( T& lhs, const T& rhs){ 
    if( lhs < rhs ){
        lhs = rhs;
        return true;
    } else {
        return false;
    }
}
template< class T > bool chmin( T& lhs, const T& rhs){ 
    if( lhs > rhs ){
        lhs = rhs;
        return true;
    } else {
        return false;
    }
}

// modpow | a^n % mod を計算する
template< class T > T modpow(T a, T n, T mod) {
    T res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// 拡張ユークリッドの互除法
template< class T > T gcdExtended(T a, T b, T& x, T& y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }

    T x1, y1; // 仮変数
    T gcd = gcdExtended(b % a, a, x1, y1);

    // 更新 x と y
    x = y1 - (b / a) * x1;
    y = x1;

    return gcd;
}

// 任意のModにおける逆元を求める関数
template< class T > T modinv(T a, T mod) {
    T x, y;
    T g = gcdExtended(a, mod, x, y);

    if (g != 1) {
#ifdef __DEBUG__
        throw std::invalid_argument("逆元は存在しません。");
#endif
        return -1;
    }

    // m が負の場合を考慮
    T res = (x % mod + mod) % mod;
    return res;
}

// range_check 
bool range_check(INT idx, INT N ){ return (0 <= idx) && (idx < N); }
bool range_check2d(INT idx1, INT idx2, INT N, INT M){ return (0 <= idx1) && (idx1 < N) && ( 0 <= idx2) && (idx2 < M); }

// safe_get 
template< class T, class T2 > T safe_get ( const std::vector<T>& v, INT idx, T2 def = -1LL ){ return range_check( idx, v.size() ) ? v[idx] : def; }
template< class T, class T2 > T safe_get2d ( const vector2d<T>& vv, INT idx1, INT idx2, T2 def = -1LL ){ return range_check( idx1, vv.size() ) ? safe_get( vv[idx1], idx2, def) : def; }

// VECTOR array constructors
template< typename T > std::vector<T> VECTOR(INT N, const T& INIT_VALUE = T() ){
    return std::vector<T>(N, INIT_VALUE);
}
template< typename T > vector2d<T> VECTOR2D(INT N, INT N2, const T& INIT_VALUE = T() ){
    return vector2d<T>(N, VECTOR<T>(N2, INIT_VALUE));
}
template< typename T > vector3d<T> VECTOR3D(INT N, INT N2, INT N3, const T& INIT_VALUE = T() ){
    return vector3d<T>(N, VECTOR2D<T>(N2, N3, INIT_VALUE) );
}
template< typename T > vector4d<T> VECTOR4D(INT N, INT N2, INT N3, INT N4, const T& INIT_VALUE = T() ){
    return vector4d<T>(N, VECTOR3D<T>(N2, N3, N4, INIT_VALUE));
}

// sort 
template< typename T > vector<T>& sort_vector_less( vector<T>& v ){
    std::sort( RANGE(v), [](auto l, auto r){ return l < r; } );
    return v;
}
template< typename T > vector<T>& sort_vector_greater( vector<T>& v){
    std::sort( RANGE(v), [](auto l, auto r){ return l > r; } );
    return v;
}
template< typename T > vector<T>& sort_vector2d_less( vector<T>& v, INT index=0 ){
    std::sort( RANGE(v), [index](auto l, auto r){ return l[index] < r[index]; } );
    return v;
}
template< typename T > vector<T>& sort_vector2d_greater( vector<T>& v, INT index=0 ){
    std::sort( RANGE(v), [index](auto l, auto r){ return l[index] > r[index]; } );
    return v;
}

// === cin >> vector/array === //
template< class T, std::size_t N>
std::istream& operator>> ( std::istream& lhs, std::array<T, N>& rhs){
    for( auto& elem: rhs ){
        lhs >> elem;
    }
    return lhs;
}
template< class T >
std::istream& operator>> ( std::istream& lhs, std::vector<T>& rhs){
    for( auto& elem: rhs ){
        lhs >> elem;
    }
    return lhs;
}
template< class T, std::size_t N>
std::istream& operator>> ( std::istream& lhs, std::vector<std::array<T,N>>& rhs){
    for( auto& elem: rhs ){
        lhs >> elem;
    }
    return lhs;
}
template< class T >
std::istream& operator>> ( std::istream& lhs, std::vector<std::vector<T>>& rhs){
    for( auto& elem: rhs ){
        lhs >> elem;
    }
    return lhs;
}

// ======================== DEBUG ======================== //

const int __SETW__ = 5;

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-parameter"

class DebugOutput : public std::ostream {
public:
    DebugOutput( std::ostream& origin ) :
        std::ostream( origin.rdbuf() )
        {}

    // to ignore "debug << endl" 
    DebugOutput& operator<< (basic_ostream<char_type,traits_type>& (*pf)(basic_ostream<char_type,traits_type>&)){
#ifdef __DEBUG__
        pf(*this);
#endif
        return *this;
    }
} debug(std::cerr);

#ifdef __DEBUG__
# include "debug.hpp"
#else

template<class T>
DebugOutput& operator<< ( DebugOutput& lhs, const T& rhs ){
    // *(static_cast<std::ostream*>(&lhs)) << rhs; // NOP //
    return lhs;
}
template<class CharT, class Traits>
DebugOutput& operator<< ( DebugOutput& lhs, basic_ostream<CharT, Traits>& endl ){
    // *(static_cast<std::ostream*>(&lhs)) << rhs; // NOP //
    return lhs;
}
#define debug(x) 

#endif

#pragma GCC diagnostic pop

#pragma endregion HEADER


#pragma region OPTIONAL_LIBS

// STL =========================== //
//#include <bits/stdc++.h>

#include <queue> // queue, priority_queue
#include <stack> // stack
#include <map>   // map
#include <set>   // set

// #include <unordered_map>
// #include <unordered_set>

// #include <any>
// #include <optional>
// #include <functional>

// #include <deque>
// #include <list>

// #include <sstream>
// #include <fstream>

// #include <chrono>
// std::chrono::system_clock::time_point START_TIME = std::chrono::system_clock::now();
// INT spent_ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - START_TIME).count();

// ATCODER LIBRARY =========================== //
// https://atcoder.github.io/ac-library/document_ja/index.html //

// #include <atcoder/fenwicktree>   
// #include <atcoder/segtree>
// #include <atcoder/lazysegtree>

// #include <atcoder/string>
// #include <atcoder/math>
// #include <atcoder/convolution>

// #include <atcoder/modint>

// #include <atcoder/dsu>
// #include <atcoder/maxflow>
// #include <atcoder/mincostflow>
// #include <atcoder/scc>
// #include <atcoder/twosat>

#pragma endregion OPTIONAL_LIBS

// =========================== MAIN =========================== //

// SNIPETS 
// LINK : https://www.notion.so/g-domain/C-1b6dbde0ac3949e3b6d44fbaf31f7c03?pvs=4



int main(){
    INT N, Q; cin >> N >> Q;

    set<INT, greater<INT>> lft_teleporter;
    set<INT, less<INT>> rgt_teleporter;

    lft_teleporter.insert(1);

    REP(_, Q){
        INT q; cin >> q;
        if( q == 1 ){
            INT x; cin >> x;
            
            INT lft_cost = INF;
            auto it = lft_teleporter.lower_bound(x);
            if( it != lft_teleporter.end() ){
                lft_cost = x - *it;
            }
            INT rgt_cost = INF;
            auto it2 = rgt_teleporter.lower_bound(x);
            if( it2 != rgt_teleporter.end() ){
                rgt_cost = *it2 - x;
            }

            cout << min(lft_cost, rgt_cost) << endl;
        } else {
            INT p, c; cin >> p >> c;
            lft_teleporter.insert(p-c);
            rgt_teleporter.insert(p+c);
        }

    }

}
yukicoder

結果

ソースコード
