Submission #130537

#	Time	Username	Problem	Language	Result	Execution time	Memory
130537		wilwxk	Bridges (APIO19_bridges)	C++14	16 / 100	1862 ms	8952 KiB

bridges

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

const int MAXN=5e4+5;
const int INF=1e9+9;
const int SQRN=4;
vector<pair<int, int> > g[MAXN];
int weight[MAXN];
int mn[MAXN], bini[MAXN], bfim[MAXN];
int n, m, q;

void precalc() {
	fill(bini, bini+m, MAXN);
	fill(mn, mn+m, INF);
	for(int i=0; i<m; i++) {
		bini[i/SQRN]=min(bini[i/SQRN], i);
		bfim[i/SQRN]=max(bfim[i/SQRN], i);
	}
}

void update(int ind, int val) {
	weight[ind]=val;
	int bind=ind/SQRN;
	if(val<=mn[bind]) {
		mn[bind]=val;
		return;
	}
	mn[bind]=val;
	for(int i=bini[bind]; i<=bfim[bind]; i++) mn[bind]=min(mn[bind], weight[i]);
}

int query(int cur, int val) {
	int resp=1;
	for(int i=cur; i<m; i++) {
		int bind=i/SQRN;
		if(weight[i]<val) break;
		if(mn[bind]>=val) resp+=(bfim[bind]-i+1), i=bfim[bind];
		else resp++;
	}
	// for(int i=0; i<=n/SQRN; i++) printf("%d >> %d %d >> %d\n", i, bini[i], bfim[i], mn[i]);
	// printf("qu %d %d >> %d\n", cur, val, resp);
	for(int i=cur-1; i>=0; i--) {
		int bind=i/SQRN;
		if(weight[i]<val) break;
		if(mn[bind]>=val) resp+=(i-bini[bind]+1), i=bini[bind];
		else resp++;
	}
	return resp;
}

int main() {
	scanf("%d %d", &n, &m);
	precalc();
	for(int i=0; i<m; i++) {
		int a, b, c; scanf("%d %d %d", &a, &b, &c); a--; b--;
		g[a].push_back({b, i}); g[b].push_back({a, i});
		weight[i]=c; 
	}
	for(int i=0; i<m; i++) update(i, weight[i]);
	scanf("%d", &q);
	while(q--) {
		int a, b, c; scanf("%d %d %d", &a, &b, &c);
		if(a==1) update(b-1, c);
		else printf("%d\n", query(b-1, c));
	}

}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:55:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d %d %d", &a, &b, &c); a--; b--;
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:62:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d %d %d", &a, &b, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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