Submission #1105907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105907		_rain_	Boat (APIO16_boat)	C++14	31 / 100	482 ms	524288 KiB

boat

#include<bits/stdc++.h>
using namespace std;

typedef long long ll ;
#define name "main"

const int N=(int)1e6;
const int MOD=(int)1e9+7;
int add(int a,int b){
	return a+b>=MOD?a+b-MOD:a+b;
}
int mul(int a,int b){
	return (ll)a*b%MOD;
}
int power(int a,int b){
	int res=1;
	for (;b;b>>=1,a=mul(a,a))
		if (b&1) res=mul(res,a);
	return res;
}
int a[N+2],b[N+2],f[N+2],n;
vector<int>nen;
vector<int>loop[N+2];
#define lef(id) id*2
#define rig(id) id*2+1
int st[N*4+2];
void upd(int id,int l,int r,int pos,int val){
	if (l>pos||r<pos) return;
	if (l==r){
		st[id]=add(st[id],val);
	}
	else{
		int m=(l+r)>>1;
		upd(lef(id),l,m,pos,val);
		upd(rig(id),m+1,r,pos,val);
		st[id]=add(st[lef(id)],st[rig(id)]);
	}
	return;
}
int Get(int id,int l,int r,int u,int v){
	if (l>v||r<u) return 0;
	if (u<=l&&r<=v) return st[id];
	int m=(l+r)>>1;
	return add(Get(lef(id),l,m,u,v),Get(rig(id),m+1,r,u,v));
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i]>>b[i];
		for(int j=a[i];j<=b[i];++j) nen.push_back(j);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	for(int i=1;i<=n;++i){
		a[i]=upper_bound(nen.begin(),nen.end(),a[i])-nen.begin();
		b[i]=upper_bound(nen.begin(),nen.end(),b[i])-nen.begin();
		for (int j=a[i];j<=b[i];++j) loop[j].push_back(i);
	}
	upd(1,0,n,0,1);
	for(int i=1;i<=nen.size();++i){
		for (int j=0;j<loop[i].size();++j){
			f[j]=Get(1,0,n,0,loop[i][j]-1);
		}
		for(int j=0;j<loop[i].size();++j) upd(1,0,n,loop[i][j],f[j]);
		// cout<<"NEN: "<<nen[i-1]<<'\n';
		// for(int j=0;j<loop[i].size();++j) cout<<f[j]<<' ';
		// cout<<'\n';
	}
	cout<<Get(1,0,n,1,n)<<'\n';
	exit(0);
}

Compilation message (stderr)

boat.cpp: In function 'int32_t main()':
boat.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i=1;i<=nen.size();++i){
      |              ~^~~~~~~~~~~~
boat.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int j=0;j<loop[i].size();++j){
      |                ~^~~~~~~~~~~~~~~
boat.cpp:68:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for(int j=0;j<loop[i].size();++j) upd(1,0,n,loop[i][j],f[j]);
      |               ~^~~~~~~~~~~~~~~

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