結果

問題 No.3116 More and more teleporter
ユーザー rui_er
提出日時 2025-04-20 13:07:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 129 ms / 2,000 ms
コード長 4,833 bytes
コンパイル時間 2,625 ms
コンパイル使用メモリ 200,060 KB
実行使用メモリ 13,008 KB
最終ジャッジ日時 2025-04-20 13:07:19
合計ジャッジ時間 4,887 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Problem: No.3116 More and more teleporter
// Contest: yukicoder
// URL: https://yukicoder.me/problems/no/3116
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 4e5 + 5;
const double eps = 1e-12;

int n, m;

int cmp(double x, double y) {
    if(x - y > eps) return +1;
    if(y - x > eps) return -1;
    return 0;
}

struct Line {
    double k, b;
    Line(double k = 0.0, double b = 1e100) : k(k), b(b) {}
    double at(double x) const {return k * x + b;}
}line[N];
int linecnt;
int newline(double x0, double y0, double x1, double y1) {
    ++linecnt;
    if(cmp(x0, y0) == 0) line[linecnt] = Line(0.0, min(y0, y1));
    else line[linecnt] = Line((y1 - y0) / (x1 - x0), y0 - ((y1 - y0) / (x1 - x0)) * x0);
    return linecnt;
}

struct LiChaoTree {
    int lazy[N << 2];
    #define lc(u) (u << 1)
    #define rc(u) (u << 1 | 1)
    void pushdown(int u, int l, int r, int p) {
        int& q = lazy[u];
        int mid = (l + r) >> 1;
        int whichM = cmp(line[p].at(mid), line[q].at(mid));
        if(whichM == -1) swap(p, q);
        int whichL = cmp(line[p].at(l), line[q].at(l)), whichR = cmp(line[p].at(r), line[q].at(r));
        if(whichL == -1) pushdown(lc(u), l, mid, p);
        if(whichR == -1) pushdown(rc(u), mid + 1, r, p);
    }
    void modify(int u, int l, int r, int ql, int qr, int p) {
        if(ql <= l && r <= qr) {
            pushdown(u, l, r, p);
            return;
        }
        int mid = (l + r) >> 1;
        if(ql <= mid) modify(lc(u), l, mid, ql, qr, p);
        if(qr > mid) modify(rc(u), mid + 1, r, ql, qr, p);
    }
    double query(int u, int l, int r, int x) {
        double now = line[lazy[u]].at(x);
        if(l == r) return now;
        int mid = (l + r) >> 1;
        if(x <= mid) return min(now, query(lc(u), l, mid, x));
        else return min(now, query(rc(u), mid + 1, r, x));
    }
    #undef lc
    #undef rc
}sgt;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    sgt.modify(1, 1, n, 1, n, newline(1, 0, n, n - 1));
    while(m--) {
        int op;
        cin >> op;
        if(op == 1) {
            int x;
            cin >> x;
            cout << (int)sgt.query(1, 1, n, x) << endl;
        }
        else {
            int x, y;
            cin >> x >> y;
            sgt.modify(1, 1, n, 1, x, newline(1, y + x - 1, x, y));
            sgt.modify(1, 1, n, x, n, newline(x, y, n, y + n - x));
        }
    }
    return 0;
}
0