oj.uz

답안 #410251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410251 2021-05-22T11:13:00 Z yoavL 다리 (APIO19_bridges) C++14
16 / 100
 503 ms 4664 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <fstream>
#include <iomanip>


using namespace std;

using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using pb = pair<bool, bool>;
using vpb = vector<pb>;
using vvpb = vector<vpb>;
using vi = vector<int>;
using vvi = vector<vi>;

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;


#define FAST        ios_base::sync_with_stdio(0)
#define FASTIN		cin.tie(0)
#define FASTOUT		cout.tie(0)

#define upmin(a, b) a = min(a, b)
#define upmax(a, b) a = max(a, b)

#define pr(x) cout << x << endl;
#define prv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define prvv(v) for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl;
#define wpr(x) cout << #x << " = " << (x) << endl;
#define wprv(v) cout << #v << ": " << endl; for(auto it : v) cout << *it << " "; cout << endl;
#define wprvv(v) cout << #v << ": " << endl; for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl;


#define rep(i,s,e) for(ll i = s; i < e; i++)
#define all(x) x.begin(),x.end()
#define pb push_back


ll n, m, q;
vll arr;


struct SEG {
	vll a;
	ll sz;
	const ll bval = 1e18; //

	ll f(ll a, ll b) //
	{
		return min(a, b);
	}

	SEG() {}

	SEG(ll n) {
		for (sz = 1; sz < n; sz <<= 1);
		a.resize(2 * sz, bval);
	}
	void make(ll n)
	{
		for (sz = 1; sz < n; sz <<= 1);
		a.resize(2 * sz, bval);
	}

	void up(ll ind, ll nval) {
		ind += sz;
		a[ind] = nval;
		for (ind >>= 1; ind; ind >>= 1) a[ind] = f(a[ind * 2], a[ind * 2 + 1]);
	}

	ll query(ll l, ll r) {
		l += sz, r += sz;
		ll res = bval;
		while (l <= r) {
			if (l % 2 == 1) res = f(res, a[l++]);
			if (r % 2 == 0) res = f(res, a[r--]);
			l >>= 1, r >>= 1;
		}
		return res;
	}


};



void solve()
{
	cin >> n >> m;
	arr.resize(n-1);
	rep(i, 0, m) {
		ll xt, yt, dt;
		cin >> xt >> yt >> dt;
		arr[i] = dt;
	}

	SEG seg;
	seg.make(n-1);
	rep(i, 0, n-1) {
		seg.up(i, arr[i]);
	}

	cin >> q;
	while (q--) {
		ll type;
		cin >> type;
		if (type == 1) {
			ll i, v;
			cin >> i >> v;
			i--;
			seg.up(i, v);
		}
		else {
			ll w, s;
			cin >> s >> w;
			s--;
			ll ans = 1;
			{
				ll low = 0, high = s-1, mid;
				ll res = s;
				while (low <= high) {
					mid = (low + high) / 2;
					ll v = seg.query(mid, s-1);
					if (w <= v) { // ok
						upmin(res, mid);
						high = mid - 1;
					}
					else {
						low = mid + 1;
					}
				}
				ans += s - res;
				//wpr(res);
			}
			{
				ll low = s, high = n-2, mid;
				ll res = s;
				while (low <= high) {
					mid = (low + high) / 2;
					//wpr(mid);
					ll v = seg.query(s, mid);
					//wpr(v);
					if (w <= v) { // ok
						upmax(res, mid+1);
						low = mid + 1;
						
					}
					else {
						high = mid - 1;
					}
				}
				ans += res - s;
				//wpr(res);
			}
			pr(ans);
		}
	}
}

int main()
{
	FAST;
	FASTIN; FASTOUT;
	solve();
}


/*

5 4
1 2 1
2 3 2
3 4 3
4 5 4
100
2 3 2

*/

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 239 ms 1760 KB Output is correct
2 Correct 245 ms 4588 KB Output is correct
3 Correct 245 ms 4536 KB Output is correct
4 Correct 242 ms 4660 KB Output is correct
5 Correct 243 ms 4520 KB Output is correct
6 Correct 320 ms 4540 KB Output is correct
7 Correct 313 ms 4564 KB Output is correct
8 Correct 306 ms 4544 KB Output is correct
9 Correct 182 ms 1804 KB Output is correct
10 Correct 282 ms 3512 KB Output is correct
11 Correct 258 ms 3540 KB Output is correct
12 Correct 503 ms 4664 KB Output is correct
13 Correct 107 ms 4416 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 222 ms 1276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 1228 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 239 ms 1760 KB Output is correct
2 Correct 245 ms 4588 KB Output is correct
3 Correct 245 ms 4536 KB Output is correct
4 Correct 242 ms 4660 KB Output is correct
5 Correct 243 ms 4520 KB Output is correct
6 Correct 320 ms 4540 KB Output is correct
7 Correct 313 ms 4564 KB Output is correct
8 Correct 306 ms 4544 KB Output is correct
9 Correct 182 ms 1804 KB Output is correct
10 Correct 282 ms 3512 KB Output is correct
11 Correct 258 ms 3540 KB Output is correct
12 Correct 503 ms 4664 KB Output is correct
13 Correct 107 ms 4416 KB Output is correct
14 Incorrect 222 ms 1276 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -