Submission #1279147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279147		ducksaysquack	Fire (BOI24_fire)	C++20	40 / 100	2102 ms	149032 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
struct segtree {
	vector<pair<int,int>> v; vector<pair<pair<int,int>,int>> a;
	void resz(int n, vector<pair<pair<int,int>,int>> w) {v.resize(4*n); a = w;}
	void init(int k, int l, int r) {
		if(l > r) return; if(l == r) v[k].f = a[l].f.s, v[k].s = a[l].s;
		else {int m = (l+r)/2; init(2*k,l,m); init(2*k+1,m+1,r); v[k] = max(v[2*k],v[2*k+1]);}
	}
	void upd(int k, int l, int r, int p, int x) {
		if(l > r) return; if(l == r) {v[k].f = x; return;}
		int m = (r+l)/2; if(p <= m) upd(2*k,l,m,p,x); else upd(2*k+1,m+1,r,p,x);
		v[k] = max(v[2*k],v[2*k+1]);
	}
	pair<int,int> prod(int k, int x, int y, int l, int r) {
		if(l == x && y == r) return v[k]; if(l > r) return {0,0};
		int m = (x+y)/2; return max(prod(2*k,x,m,l,min(m,r)),prod(2*k+1,m+1,y,max(l,m+1),r));
	}
};
signed main() {
	int n, m; cin >> n >> m; vector<pair<pair<int,int>,int>> v(n);
	for(int i=0;i<n;i++) {cin >> v[i].f.f >> v[i].f.s; if(v[i].f.s < v[i].f.f) v[i].f.s += m;}
	sort(begin(v),end(v)); for(int i=0;i<n;i++) v.push_back({{v[i].f.f+m,v[i].f.s+m},i});
	for(int i=0;i<n;i++) v.push_back({{v[i].f.f+2*m,v[i].f.s+2*m},i}); for(int i=0;i<n;i++) v[i].s = i;
	int ans = 1e9, k = log2(n); segtree t; vector<vector<pair<int,int>>> c(n,vector<pair<int,int>>(k+1)); vector<int> w(3*n);
	t.resz(3*n,v); t.init(1,0,3*n-1); for(int i=0;i<3*n;i++) w[i] = v[i].f.f;
	//for(auto i:v) cerr << i.f.f << ' ' << i.f.s << ' ' << i.s << '\n'; cerr << '\n';
	for(int i=0;i<n;i++) {
		auto p = t.prod(1,0,3*n-1,0,upper_bound(begin(w),end(w),v[i+n].f.s)-begin(w)-1);
		if(p.f <= v[i+n].f.s) {cout << -1; return 0;} else c[i][0].f = p.s, c[i][0].s = (v[p.s].f.s-v[i].f.s+m)%m;
		//cerr << v[i].f.s << ' ' << lower_bound(begin(w),end(w),v[i].f.s)-begin(w) << ' ' << p.f << ' ' << p.s << '\n';
	}
	for(int i=0;i<n;i++) cerr << c[i][0].f << ' ' << c[i][0].s << '\n'; cerr << '\n';
	for(int i=1;i<=k;i++) for(int j=0;j<n;j++) c[j][i].f = c[c[j][i-1].f][i-1].f, c[j][i].s = c[j][i-1].s+c[c[j][i-1].f][i-1].s;
	for(auto i:c) {for(auto j:i) cerr << j.s << ' '; cerr << '\n';}
	for(int i=0;i<n;i++) {
		int a = 1, b = i, d = v[i].f.s-v[i].f.f;
		for(int j=k;j>=0;j--) if(c[b][j].s+d < m) a += (1<<j), d += c[b][j].s, b = c[b][j].f;
		ans = min(ans, a+1);
	}
	cout << ans << '\n';
}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26