Submission #1133454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133454		Math4Life2020	Boat (APIO16_boat)	C++20	58 / 100	2096 ms	55176 KiB

boat

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>; 
ll ans = 0;
const ll p = 1e9+7;
const ll Nm = 505;
ll vinv[Nm];

struct Node {
	ll l,r; //left, right
	bool isS; //is short (aka length 1)
	vector<ll> velem;  //length-Nm vector of elements
	vector<ll> vbin;
	ll nv; //node value
	Node(){}
	Node(ll l0, ll r0) {
		l = l0; r = r0;
		if (l==r) {
			isS = 1;
			nv = 0;
		} else {
			isS = 0;
			velem = vbin = vector<ll>(Nm,0);
			nv = 0;
			vbin[0]=r-l+1;
			for (ll i=1;i<(Nm-1);i++) {
				vbin[i]=(vbin[i-1]*vinv[i+1])%p;
				vbin[i]=(vbin[i]*(r-l+1-i))%p;
			}
		}
	}
	void incS() {
		if (isS) {
			return;
		}
		vector<ll> vel2 = vector<ll>(Nm,0);
		for (ll i=0;i<Nm;i++) {
			if (velem[i]>0) {
				vel2[i]=(vel2[i]+velem[i])%p;
				vel2[i+1]=(vel2[i+1]+velem[i])%p;
			}
		}
		velem=vel2;
		ll nvf = 0;
		for (ll i=0;i<Nm;i++) {
			nvf = (nvf+velem[i]*vbin[i])%p;
		}
		nv=nvf;
	}
	void incV(ll ev) {
		nv = (nv+(r-l+1)*ev)%p;
		if (!isS) {
			velem[0]=(velem[0]+ev)%p;
		}
	}
};

vector<Node> vecN;

ll inv(ll x) {
	array<ll,3> a = {x,1,0};
	array<ll,3> b = {p,0,1};
	while (a[0]!=0) {
		if (a[0]>b[0]) {
			swap(a,b);
		} else {
			ll k = b[0]/a[0];
			for (ll i=0;i<3;i++) {
				b[i]-=k*a[i];
			}
		}
	}
	ll fvb = b[1];
	return (fvb+(2-fvb/p)*p)%p;
}

int main() {
	for (ll i=1;i<Nm;i++) {
		vinv[i]=inv(i);
	}
	ll N; cin >> N;
	vector<pii> vupd;
	vector<ll> vdel = vector<ll>(Nm,0);
	for (int i=0;i<Nm;i++) {
		vdel[i]=i;
	}
	ll bmax = -1;
	for (ll n=0;n<N;n++) {
		ll a,b; cin >> a >> b;
		bmax = max(b,bmax);
		vupd.push_back({a,b});
		for (ll d=0;d<=N;d++) {
			vdel.push_back(a+d);
			vdel.push_back(b+1+d);
		}
	}
	sort(vdel.begin(),vdel.end());
	vdel.erase(unique(vdel.begin(),vdel.end()),vdel.end());
	vector<ll> vdel2;
	for (ll x: vdel) {
		if (x<=(bmax+1)) {
			vdel2.push_back(x);
		}
	}
	vdel2 = vdel;
	for (ll x=0;x<(ll)(vdel2.size()-1);x++) {
		vecN.push_back(Node(vdel2[x],vdel2[x+1]-1));
		//associated with [vdel2[x],vdel2[x+1])
	}
	vecN[0].incV(1);
	for (pii pupd: vupd) {
		ll a = pupd.first; ll b = pupd.second; //update [a,b+1)
		ll rtot = 0;
		for (ll i=0;i<vecN.size();i++) {
			ll vnl = vecN[i].l; ll vnr = vecN[i].r;
			ll rnew = vecN[i].nv;
			if (a<=vnl && vnr<=b) {
				vecN[i].incS();
				vecN[i].incV(rtot);
				rtot = (rtot+rnew)%p;
			} else {
				rtot = (rtot+rnew)%p;
			}
			//cout << "rtot="<<rtot<<"\n";
		}
	}
	for (ll i=0;i<vecN.size();i++) {
		ans = (ans+vecN[i].nv)%p;
	}
	ans = (ans+p-1)%p;
	cout << ans << "\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42