oj.uz

답안 #277974

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
277974 2020-08-21T08:20:48 Z groeneprof 다리 (APIO19_bridges) C++14
16 / 100
 1189 ms 6404 KB 
#include <bits/stdc++.h>

#define P(a) do{if(debug) cout<<a<<endl;} while(false)
#define H(a) P(#a<<": "<<a)
#define FR(i,a,b) for(int i = (a); i<(b); i++)
#define F(i,n) FR(i,0,n)

const int debug = 0;
const int inf = 2e9;
using namespace std;

vector<int> st;
int n, m,q;
vector<pair<int,int> > edges;
vector<int> weights;

int update(int i, int v, int u, int L, int R){
	H(i);
	H(v);
	H(u);
	H(L);
	H(R);
	if(L>i || R < i) {P("out of bounds"); return st[u];}
	if(L==R){P("leaf found"); return st[u] = v;}
	st[u] = min(update(i,v,u*2+1,L,(L+R)/2),update(i,v,u*2+2,(L+R)/2+1,R));
	H(i);
	H(v);
	H(u);
	H(L);
	H(R);
	H(st[u]);
	return st[u];
}

int query(int i, int j, int u, int L, int R){
	if(j<L||R<i) return inf;
	if(L>=i && R<=j) return st[u];
	return min(query(i,j,u*2+1,L,(L+R)/2),query(i,j,u*2+2,(L+R)/2+1,R));
}

int bs1(int w, int i){
	int ans = -1;
	for(int bit = 1<<20; bit>0; bit/=2){
		H(ans+bit);
		if(ans+bit<n) H(query(ans+bit,i-1,0,0,n-1));
		if(ans+bit<i&&query(ans+bit,i-1,0,0,n-1)<w){
			ans+=bit;
		}
	}
	return ans+1;
}

int bs2(int w, int i){
	int ans = i-1;
	for(int bit = 1<<20; bit>0; bit/=2){
		H(ans+bit);
		if(ans+bit<n) H(query(i,ans+bit,0,0,n-1));
		if(ans+bit<n-1&&query(i,ans+bit,0,0,n-1)>=w){
			ans+=bit;
		}
	}
	return ans+1;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	edges.resize(m);
	weights.resize(m);
	st.resize(4*n,inf);
	F(i,m){
		cin>>edges[i].first>>edges[i].second>>weights[i];
		edges[i].first--;
		edges[i].second--;
		update(i,weights[i],0,0,n-1);

	}
	/*for(int i : st){
		cout<<i<<" ";
	}
	cout<<endl;*/
	cin>>q;
	F(i,q){
		int type;
		cin>>type;
		if(type==1){
			int a, b;
			cin>>a>>b;
			a--;
			update(a,b,0,0,n-1);
			weights[a] = b;
			/*for(int aa : st){
				cout<<aa<<" ";
			}
			cout<<endl;*/
			
		}
		else{
			int a, b;
			cin>>a>>b;
			a--;
			cout<<bs2(b,a)-bs1(b,a)+1<<endl;
		}
	}
	return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 559 ms 4632 KB Output is correct
2 Correct 558 ms 4600 KB Output is correct
3 Correct 566 ms 4604 KB Output is correct
4 Correct 607 ms 4604 KB Output is correct
5 Correct 537 ms 4600 KB Output is correct
6 Correct 732 ms 4520 KB Output is correct
7 Correct 649 ms 4608 KB Output is correct
8 Correct 714 ms 4728 KB Output is correct
9 Correct 259 ms 1872 KB Output is correct
10 Correct 556 ms 3616 KB Output is correct
11 Correct 570 ms 3860 KB Output is correct
12 Correct 1189 ms 4816 KB Output is correct
13 Correct 234 ms 4608 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 559 ms 4632 KB Output is correct
2 Correct 558 ms 4600 KB Output is correct
3 Correct 566 ms 4604 KB Output is correct
4 Correct 607 ms 4604 KB Output is correct
5 Correct 537 ms 4600 KB Output is correct
6 Correct 732 ms 4520 KB Output is correct
7 Correct 649 ms 4608 KB Output is correct
8 Correct 714 ms 4728 KB Output is correct
9 Correct 259 ms 1872 KB Output is correct
10 Correct 556 ms 3616 KB Output is correct
11 Correct 570 ms 3860 KB Output is correct
12 Correct 1189 ms 4816 KB Output is correct
13 Correct 234 ms 4608 KB Output is correct
14 Incorrect 514 ms 3724 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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