제출 #1032694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032694		Muhammet	다리 (APIO19_bridges)	C++17	0 / 100	576 ms	524288 KiB

bridges

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

#define sz(x) (int)x.size()
#define ff first
#define ss second
#define int long long int

const int N = 2000005;
const int M = 1e9 + 7;

int T, n, a[N], b[N], c[N], q, s[N], w[N], t[N], d[N], r2[N], ans, vis[N], m, x3;

vector <int> st;

int bld(int nd, int l, int r){
	if(l == r) return st[nd] = c[l];
	int md = (l + r) / 2;
	return st[nd] = min(bld(nd*2,l,md), bld(nd*2+1,md+1,r));
}

int upd(int nd, int l, int r, int ind, int vl){
	if((r < ind) or (l > ind)) return st[nd];
	if(l == r) return st[nd] = vl;
	int md = (l + r) / 2;
	return st[nd] = min(upd(nd*2,l,md,ind,vl), upd(nd*2+1,md+1,r,ind,vl));
}

int fnd(int nd, int l, int r, int x, int y){
	if(l > y or r < x) return st[nd];
	if(l >= x and r <= y){
		x3 = min(x3,st[nd]);
		return st[nd];
	}
	int md = (l + r) / 2;
	return st[nd] = min(fnd(nd*2,l,md,x,y),fnd(nd*2+1,md+1,r,x,y));
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	st.resize(m*4);
	cin >> q;
	for(int i = 1; i <= q; i++){
		cin >> t[i];
		if(t[i] == 1){
			cin >> d[i] >> r2[i];
		}
		else {
			cin >> s[i] >> w[i];
		}
	}

	bld(1,1,m);
	for(int i = 1; i <= q; i++){
		if(t[i] == 1){
			upd(1,1,m,d[i],r2[i]);
		}
		else {
			int l1 = s[i], r1 = m, k = 0, an = n;
			while(l1 <= r1){
				int md = (l1 + r1) / 2;
				x3 = 1e9;
				fnd(1,1,m,s[i],md);
				if(x3 < w[i]){
					r1 = md-1;
					k = md;
				}
				else {
					l1 = md+1;
				}
			}
			if(k != 0) an -= (n-k);
			l1 = 1, r1 = s[i]-1, k = 0;
			while(l1 <= r1){
				int md = (l1 + r1) / 2;
				x3 = 1e9;
				fnd(1,1,m,md,s[i]-1);
				if(x3 < w[i]){
					l1 = md+1;
					k = md;
				}
				else {
					r1 = md-1;
				}
			}
			an -= k;
			cout << an << '\n';
		}
	}

	return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27