Submission #883087

#	Time	Username	Problem	Language	Result	Execution time	Memory
883087		KN200711	Boat (APIO16_boat)	C++14	100 / 100	866 ms	1876 KiB

boat

# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;

const ll MOD = 1e9 + 7;

vector<int> seg[1100];
int l[1100], r[1100], len[1100];
bool V[501];
int num;

ll pref[1100], ad[1100], inv[1100];

ll fast(ll a, int b) {
	if(b == 0) return 1ll;
	if(b == 1) return a;
	ll K = fast(a, b / 2);
	K *= K;
	K %= MOD;
	if(b&1) {
		K *= a;
		K %= MOD;
	}
	return K;
}

void build() {
	inv[0] = 1;
	for(int i=1;i<1100;i++) {
		inv[i] = fast(i, MOD - 2);
	}
}

void fx(ll &a, ll c, ll d) {
	a *= c;
	a %= MOD;
	a *= inv[d];
	a %= MOD;
}

int main() {
	build();
	
	int N;
	scanf("%d", &N);
	
	vector< pair<int, int> > arr;
	arr.clear();
	for(int i=1;i<=N;i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		arr.push_back(make_pair(a, i));
		arr.push_back(make_pair(b + 1, -i));
	}
	sort(arr.begin(), arr.end());
	int lst;
	for(int i=0;i<arr.size();i++) {
		if(i > 0 && arr[i].fi != arr[i - 1].fi) {
			l[num] = lst;
			r[num] = arr[i].fi - 1;
			len[num] = r[num] - l[num] + 1;
			for(int k=1;k<=N;k++) {
				if(V[k]) seg[num].push_back(k);
			}
			num++;
		}
		if(arr[i].se < 0) V[-arr[i].se] = 0;
		else V[arr[i].se] = 1;
		lst = arr[i].fi;
	}
	
	for(int i=0;i<=N;i++) pref[i] = 1ll;
	for(int i=0;i<num;i++) {
	//	cout<<l[i]<<" "<<r[i]<<endl;
		for(int k=1;k<=N;k++) ad[k] = 0ll;
		for(int k=1;k<=seg[i].size();k++) {
			ll as = 0ll;
			if(k == 1) {
				as = len[i];
			} else if(len[i] >= 2) {
				ll v = 1ll;
				fx(v, len[i], 1ll);
				fx(v, len[i] - 1, 2ll);
				for(int c=0;;c++) {
					as += v;
					as %= MOD;
					if(len[i] < c + 2) break;
					if(k < c + 2) break;
					fx(v, len[i] - c - 2ll, c + 3ll);
					fx(v, k - c - 2ll, c + 1ll);
				}
			}
		//	cout<<"as : "<<i<<" "<<k<<" "<<as<<endl;
			for(int c=0;c+k-1<seg[i].size();c++) {
				ll D = as * pref[seg[i][c] - 1];
				D %= MOD;
				ad[seg[i][c + k - 1]] += D;
				ad[seg[i][c + k - 1]] %= MOD;
			}
		}
		ll kp = 0ll;
		for(int k = 1;k<=N;k++) {
		//	cout<<i<<" "<<k<<" "<<ad[k]<<endl;
			kp += ad[k];
			kp %= MOD;
			pref[k] += kp;
			pref[k] %= MOD;
		}
	}
	pref[N]--;
	if(pref[N] < 0) pref[N] += MOD;
	printf("%lld\n", pref[N]);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:59:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i=0;i<arr.size();i++) {
      |              ~^~~~~~~~~~~
boat.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int k=1;k<=seg[i].size();k++) {
      |               ~^~~~~~~~~~~~~~~
boat.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    for(int c=0;c+k-1<seg[i].size();c++) {
      |                ~~~~~^~~~~~~~~~~~~~
boat.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
boat.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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