Submission #1084511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084511		peacebringer1667	Boat (APIO16_boat)	C++17	31 / 100	473 ms	524288 KiB

boat

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 5e2 + 5;
const int modu = 1e9 + 7;

pir a[maxn];
void input(int n){
	for (int i = 1 ; i <= n ; i++) cin >> a[i].fi >> a[i].se;
}

namespace sub1_2{
	map <int,int> M;
	const int N = 1e6 + 5;
	
	struct fenwick_tree{
		ll fenwick[N];
		
		void update(int x,int n,ll val){
			while (x <= n){
				fenwick[x] = (fenwick[x] + val) % modu;
				x = x | (x + 1);
			}
		}
		
		ll calc(int x){
			ll res = 0;
			while (x > 0){
				res = (res + fenwick[x]) % modu;
				x = x & (x + 1);
				x--;
			}
			return res;
		}
	} fw;
	
	void compress(int n){
		vector <int> V;
		
		for (int i = 1 ; i <= n ; i++)
			for (int j = a[i].fi ; j <= a[i].se ; j++)
			  V.push_back(j);
			
		sort(V.begin(),V.end());
		int cur = 0,lst = 0;
		
		for (int x : V){
			if (x != lst){
				lst = x;
				cur++;
			}
			
			M[x] = cur;
		}
	}
	
	ll solve(int n){
		compress(n);
		int lim = 0;
		for (int i = 1 ; i <= n ; i++) lim = max(lim,M[a[i].se]);
		
		for (int i = a[1].fi ; i <= a[1].se ; i++)
		  fw.update(M[i],lim,1);
		
		for (int i = 2 ; i <= n ; i++){
			for (int v = a[i].se ; v >= a[i].fi ; v--){
				ll val = fw.calc(M[v] - 1) + 1;
				fw.update(M[v],lim,val);
			}
		}
		
		return fw.calc(lim);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n;
	cin >> n;
	input(n);
	
	cout << sub1_2::solve(n);

	return 0;
}

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