Submission #632225

#	Time	Username	Problem	Language	Result	Execution time	Memory
632225		gs14004	Bread First Search (CCO21_day2problem2)	C++17	25 / 25	176 ms	11780 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXT = 530000;
const int mod = 1e9 + 7;

struct seg{
	int tree[MAXT], lazy[MAXT];
	void lazydown(int p){
		for(int i = 2*p; i < 2*p+2; i++){
			lazy[i] += lazy[p];
			tree[i] += lazy[p];
		}
		lazy[p] = 0;
	}
	void add(int s, int e, int ps, int pe, int p, int v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			tree[p] += v;
			lazy[p] += v;
			return;
		}
		lazydown(p);
		int pm = (ps+pe)/2;
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm+1, pe, 2*p+1, v);
		tree[p] = min(tree[2*p], tree[2*p+1]);
	}
	int query(int s, int e, int ps, int pe, int p){
		if(e < ps || pe < s) return 1e9;
		if(s <= ps && pe <= e) return tree[p];
		lazydown(p);
		int pm = (ps+pe)/2;
		return min(query(s, e, ps, pm, 2*p), query(s, e, pm+1, pe, 2*p+1));
	}
}seg;

int main(){	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> L(n, 1e9), R(n, -1e9), dp(n + 1), nxt(n, 1e9);
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v;
		u--; v--;
		if(u > v) swap(u, v);
		R[u] = max(R[u], v);
		L[v] = min(L[v], u);
	}
	for(int i = 0; i < n; i++){
		nxt[i] = R[i];
		if(i) nxt[i] = max(nxt[i], nxt[i - 1]);
	}
	vector<pi> swp;
	for(int i = 0; i < n; i++) swp.emplace_back(min(i, L[i]), i);
	sort(all(swp)); 
	for(int i = n - 1; i >= 1; i--){
		while(sz(swp) && swp.back().first >= i){
			seg.add(swp.back().second + 1, n, 0, n, 1, 1);
			swp.pop_back();
		}
		dp[i] = seg.query(max(i, nxt[i-1]) + 1, n, 0, n, 1);
		seg.add(i, i, 0, n, 1, dp[i]);
	}
	cout << dp[1] << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 14 / 14