Submission #1279141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279141		ducksaysquack	Fire (BOI24_fire)	C++20	0 / 100	1 ms	580 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; v[i].s = i; 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},v[i].s}); for(int i=0;i<n;i++) v.push_back({{v[i].f.f+2*m,v[i].f.s+2*m},v[i].s});
	segtree t; t.resz(3*n,v); t.init(1,0,3*n-1); vector<int> w(3*n), z(n); 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 z[i] = p.s;
		//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 << z[i] << ' ';
	//for(int i=0;i<n;i++) cout << t.prod(1,0,2*n-1,i,i).f << ' ' << t.prod(1,0,2*n-1,i,i).s << '\n';
	vector<int> c(n), d(n), e(n); int x = 1, ans = 1e9; for(int i=0;i<n;i++) e[v[i].s] = z[i];
	//for(auto i:e) cout << i << ' '; cout << '\n';
	for(int i=0;i<n;i++) {
		if(c[i]) continue; c[i] = x; int y = 0;
		while(!c[e[i]]) i = e[i], c[i] = x, y++, d[i] = y;// cout << i << ' ';}
		if(c[i] == x) ans = min(ans, y-d[e[i]]+1); //cout << '\n';
		x++;		
	}
	//for(auto i:c) cout << i << ' '; cout << '\n';
	//for(auto i:d) cout << i << ' '; cout << '\n';
	cout << ans;
}

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