| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1324301 | nicolo_010 | 게임 (IOI14_game) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define f first
#define s second
struct SegTree {
vector<ll> tree;
int n;
SegTree(int _n) {
n = _n;
tree.assign(4*(n+1), 1e18);
}
void query(int p, int l, int r, int i, ll x) {
if (l>i || r<i) return;
if (l==r) {
tree[p] = x;
return;
}
int m = (l+r)/2;
query(2*p, l, m, i, x);
query(2*p+1, m+1, r, i, x);
tree[p] = min(tree[2*p], tree[2*p+1]);
}
int kth(int p, int l, int r, int i, ll x) {
if (r < i) return n;
if (tree[p] > x) return n;
if (l==r) {
return l;
}
int m = (l+r)/2;
int ans = kth(2*p, l, m, i, x);
if (ans==n) {
//No es valido ir a la izquierda, bajo por la derecha
return kth(2*p+1, m+1, r, i, x);
}
return ans;
}
};
void solve() {
int n, q; cin >> n >> q;
vector<ll> a(n);
for (int i=0; i<n; i++) {
cin >> a[i];
}
SegTree st(n);
a.push_back(1);
for (int i=0; i<n; i++) {
st.query(1, 0, n, i, a[i]);
}
st.query(1, 0, n, n, 0);
while (q--) {
int t; cin >> t;
if (t==1) {
ll x; cin >> x;
int i=-1;
ll ans=0;
while (i<n) {
int ni = st.kth(1, 0, n, i+1, x);
int ln = ni-i-1;
ans += x*ln;
//cout << ni << " " << i << " " << ans << " " << x << endl;
x %= a[ni];
ans += x;
i = ni;
}
cout << ans << "\n";
}
else {
int i; ll x;
cin >> i >> x;
i--;
a[i] = x;
st.query(1, 0, n, i, x);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--) {
solve();
}
return 0;
}
/*
3
2 3 1
*/