結果
問題 |
No.3116 More and more teleporter
|
ユーザー |
|
提出日時 | 2025-04-18 22:01:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 8,963 bytes |
コンパイル時間 | 3,014 ms |
コンパイル使用メモリ | 228,368 KB |
実行使用メモリ | 14,228 KB |
最終ジャッジ日時 | 2025-04-18 22:01:53 |
合計ジャッジ時間 | 4,540 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ar array #define int long long #define ll long long #define ld long double #define pb push_back #define eb emplace_back #define pob pop_back() #define nn "\n" #define onn << "\n" #define ee endl #define oee << endl #define ss " " #define oss << " " #define sei unordered_set<int, custom_hash> #define ses unordered_set<string> #define ma unordered_map #define maii unordered_map<int, int, custom_hash> #define vc vector #define id1 int n; cin >> n; #define gls getline(cin, s) #define sinf 1e9 #define inf (int) 1e18 #define co cout << #define sp(i) setprecision(i) << #define f1(i, a) for (auto& i : a) #define f2(i, j, a) for (auto& [i, j] : a) #define f3(i, j, k, a) for (auto& [i, j, k] : a) #define be(s) s.begin(), s.end() #define rbe(s) s.rbegin(), s.rend() #define bb(s) s.begin(), s.begin() #define ctz(x) __builtin_ctzll(x) #define cb(x) __builtin_popcountll(x) #define ff(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define i128 __int128_t #define lb lower_bound #define ub upper_bound #define ook order_of_key #define fbo find_by_order #define fn function #define bs bitset #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef unsigned long long ull; typedef pair<int, string> pis; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<string> vs; typedef vector<double> vd; typedef vector<pair<int,int>> vp; typedef vector<vector<int>> vvi; #pragma GCC optimize("Ofast,unroll-loops") #ifdef LOCAL #include "debug_util.h" #else #define help(...) #define helpArray(...) #define io #define _time #define _siu #endif template<class T> using pq = priority_queue<T>; template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os;} template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second; return is;} template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");} return os;} template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is;} struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template<class T> bool constexpr chmin(T &a, T b) { if (a > b) {a = b;return true;} return false; } template<class T> bool constexpr chmax(T &a, T b) { if (a < b) {a = b;return true;} return false; } // stable sort template <typename T> vector<int> argsort(const vector<T> &A) { vector<int> ans(sz(A)); iota(be(ans), 0); sort(be(ans), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); }); return ans; } //64b long long lsb(long long x) { return x & -x;} long long msb(long long x) { return (1ll << (63-__builtin_clzll(x))) & x;} void onb(long long& x, int i) { x |= (1ll << i);} void offb(long long& x, int i) { x &= ~(1ll << i);} bool hb(long long x, int i) { return ((1ll << i) & x) != 0;} long long bit(long long x) { return 1ll << x;} void YES(bool t = 1) { cout << (t ? "YES" : "NO") << "\n"; } void NO(bool t = 1) { YES(!t); } void Yes(bool t = 1) { cout << (t ? "Yes" : "No") << "\n"; } void No(bool t = 1) { Yes(!t); } template<typename T> vector<pair<T, int>> pfy(vector<T>& f) { vector<pair<T, int>> v; for (int i = 0; i < f.size(); i++) { v.push_back({f[i], i}); } return v; } bool inrange(int i, int j, int limi, int limj) { return i >= 0 && i < limi && j >= 0 && j < limj; } typedef tuple<int,int,int> iii; vector<char> cao = {'C','D','H','S'}; int dr8[] = {0,-1,0, 1, 1, 1, -1, -1}; int dc8[] = {-1, 0, 1, 0, 1, -1, 1, -1}; //n,w,e,s int dr[] = {-1, 0, 0, 1}; int dc[] = {0,-1,1, 0}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { uniform_int_distribution<int> uid(l, r); return uid(rng); } // Define a tree-based set with integer keys template <typename T> using Tee = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; namespace atcoder { #undef int namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal 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 = internal::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; } void print() { help(d); } private: int _n, size, log; std::vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; } // namespace atcoder #define int long long using namespace atcoder; using S = int; S op(S a, S b) { return min(a,b); } S e() { return inf; } void sui() { int n,q; cin>>n>>q; vi v(n), v2(n); iota(be(v2), 0ll); f1(i,v2) i *= 2; segtree<S, op,e> seg(v), seg2(v2); ff(i,0,q) { int t; cin>>t; if (t == 1) { int x; cin>>x; --x; co min(x+seg.prod(0, x+1), seg2.prod(x+1, n) - x) onn; } else { int x,y; cin>>x>>y; --x; seg.set(x, min(seg.get(x), y-x)); seg2.set(x, min(seg2.get(x), v2[x]+y-x)); } } } signed main() { cin.tie(NULL); ios_base::sync_with_stdio(false); auto start = std::chrono::high_resolution_clock::now(); io; int n = 1; // cin >> n; ff(i,0,n) sui(); _time; return 0; }