Submission #745003

#	Time	Username	Problem	Language	Result	Execution time	Memory
745003		amirhoseinfar1385	Boat (APIO16_boat)	C++17	31 / 100	495 ms	524288 KiB

boat

#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;

struct fen{
	long long fn[(1<<20)];
	void upd(int i,long long w){
		i++;
		while(i<(1<<20)){
			fn[i]+=w;
			fn[i]%=mod;
			i+=(-i)&i;
		}
	}
	long long pors(int i){
		i++;
		long long ret=0;
		while(i>0){
			ret+=fn[i];
			i-=(-i)&i;
		}
		ret%=mod;
		return ret;
	}
}fenw;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<pair<int,int>>all(n);
	vector<int>allind;
	for(int i=0;i<n;i++){
		cin>>all[i].first>>all[i].second;
		for(int j=all[i].first;j<=all[i].second;j++)
		{
			allind.push_back(j);
		}
	}
	allind.push_back(0);
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	fenw.upd(0,1);
	for(int i=0;i<n;i++){
		int lp=lower_bound(allind.begin(),allind.end(),all[i].first)-allind.begin();
		for(int j=all[i].second-all[i].first;j>=0;j--){
			fenw.upd(lp+j,fenw.pors(lp+j-1));
		}
	}
	long long res=fenw.pors((int)allind.size());
	res+=mod-1;
	res%=mod;
	cout<<res<<"\n";
}

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