이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
Author : DeMen100ns (a.k.a Vo Khac Trieu)
School : VNU-HCM High school for the Gifted
fuck you adhoc
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;
int n, m, q;
int seg[4 * N];
void upd(int id, int l, int r, int pos, int val){
if (l == r){
seg[id] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid){
upd(id << 1, l, mid, pos, val);
} else {
upd(id << 1 | 1, mid + 1, r, pos, val);
}
seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v){
if (l > v || r < u) return MAXA;
if (l >= u && r <= v) return seg[id];
int mid = (l + r) >> 1;
int v1 = get(id << 1, l, mid, u, v);
int v2 = get(id << 1 | 1, mid + 1, r, u, v);
return min(v1, v2);
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= m; ++i){
int u, v, w; cin >> u >> v >> w;
//a[i] = w;
upd(1, 0, n, i, w);
}
cin >> q;
while (q--){
int type, u, val; cin >> type >> u >> val;
if (type == 1){
upd(1, 0, n, u, val);
} else{
int ll = 0, rl = u - 1;
while (ll + 1 < rl){
int mid = (ll + rl) >> 1;
if (get(1, 0, n, mid, u - 1) >= val) rl = mid;
else ll = mid;
}
int l = rl;
int lr = u, rr = n - 1;
while (lr + 1 < rr){
int mid = (lr + rr) >> 1;
if (get(1, 0, n, u, mid) >= val) lr = mid;
else rr = mid;
}
int r = lr;
cout << r - l + 1 << endl;
}
//for(int i = 1; i < n; ++i) cout << get(1, 0, n, i, i) << " ";
//cout << endl;
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("codeforces.inp","r",stdin);
// freopen("codeforces.out","w",stdout);
int t = 1; // cin >> t;
while (t--)
{
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |