結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー iomir
提出日時 2025-04-19 19:47:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 234 ms / 2,000 ms
コード長 2,319 bytes
コンパイル時間 3,070 ms
コンパイル使用メモリ 280,108 KB
実行使用メモリ 11,496 KB
最終ジャッジ日時 2025-04-19 19:47:11
合計ジャッジ時間 6,197 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

#define all(v) v.begin(),v.end()
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using vll=vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,ll>;
using vp=vector<pair<ll, ll>>;
//using mint=modint1000000007;
//using mint=modint998244353;

const ll INF=1ll<<60;
ll mod10=1e9+7;
ll mod99=998244353;
const double PI = acos(-1);

#define rep(i,n) for (ll i=0;i<n;++i)
#define per(i,n) for(ll i=n-1;i>=0;--i)
#define rep2(i,a,n) for (ll i=a;i<n;++i)
#define per2(i,a,n) for (ll i=a;i>=n;--i)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

template<typename monoid>
struct segtree{
    using T = typename monoid::Type;
    ll N;
    vector<T> node;
    segtree(ll n){
        N=1;
        while(N<n) N*=2;
        node = vector<T>(N*2-1,monoid::id());
    }
    T operator [](int k){
        return node[N-1+k];
    }
    void update(int k,T x){
        k+=N-1;
        node[k]=x;
        while(k){
            k=(k-1)/2;
            node[k]=monoid::op(node[2*k+1],node[2*k+2]);
        }
    }
    T query(int a,int b,int k,int l,int r){
        if(r<=a||b<=l) return monoid::id();
        else if(a<=l&&r<=b) return node[k];
        else{
            int m=(l+r)/2;
            return monoid::op(query(a,b,2*k+1,l,m),query(a,b,2*k+2,m,r));
        }
    }
    T sub(int a,int b){
        return query(a,b,0,0,N);
    }

   
};

struct monoid{
    using Type = long long;
    static Type op(Type a,Type b){
       return min(a,b);
    }
    static Type id(){return INF;}
};

bool solve(){
    ll N,Q;cin>>N>>Q;
    segtree<monoid> segl(N),segr(N);
    rep(_,Q){
        ll t;cin>>t;
        if(t==1){
            ll x;cin>>x;
            x--;
            ll ans=x;
            chmin(ans,min(segl.sub(0,x)+x,segr.sub(x,N)-x));
            cout<<ans<<endl;
        }else{
            ll x,c;cin>>x>>c;x--;
            segl.update(x,min(segl[x],c-x));
            segr.update(x,min(segr[x],c+x));
        }
    }
    return 0;
}




int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll T=1;//cin>>T;
    rep(i,T) solve();
}
0