Submission #105025

#	Time	Username	Problem	Language	Result	Execution time	Memory
105025		puyu_liao	Boat (APIO16_boat)	C++14	31 / 100	2045 ms	127184 KiB

boat

#include<bits/stdc++.h>
#include<stdint.h>
using namespace std;
#define IOS {cin.tie(0);ios_base::sync_with_stdio(false);}
#define N 505
#define int int64_t
#define lowbit(x) (x&-x)
const int MOD = 1000000007;

unordered_map<int,int> mp;
void add(int x,int c){
	for(;x<MOD;x+=lowbit(x)) (mp[x] += c) %= MOD;
}

int qur(int x){
	int r = 0;
	for(;x;x-=lowbit(x)) (r += mp[x]) %= MOD;
	return r;
}

int a[N],b[N];	
int32_t main(){
	IOS;
	int n,ans = 0;
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i] >> b[i],a[i]++,b[i]++;
	add(1,1);
	for(int i=1;i<=n;i++) {
		for(int j=b[i];j>=a[i];j--) add(j,qur(j-1));
	}
	cout << (qur(MOD-1)+MOD-1) % MOD << '\n';
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int32_t main()':
boat.cpp:24:8: warning: unused variable 'ans' [-Wunused-variable]
  int n,ans = 0;
        ^~~

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