Submission #793365

#	Time	Username	Problem	Language	Result	Execution time	Memory
793365		ToniB	Boat (APIO16_boat)	C++17	31 / 100	723 ms	524288 KiB

boat

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 505;
const int OFF = 1 << 21;

int add(int a, int b){ return (a + b >= MOD) ? a + b - MOD : a + b; }

vector<int> dp[MAXN];

int n, a[MAXN], b[MAXN], tour[OFF];
vector<int> v;

int f(int x, int l, int r, int ql, int qr){
	if(ql <= l && r <= qr) return tour[x];
	if(ql > r || l > qr) return 0;
	int mid = (l + r) >> 1;
	return add(f(x * 2 + 1, l, mid, ql, qr), f(x * 2 + 2, mid + 1, r, ql, qr));
}
void upd(int x, int l, int r, int i, int val){
	if(l > i || r < i) return ;
	if(l == r){
		tour[x] = val;
		return ;
	}
	int mid = (l + r) >> 1;
	upd(x * 2 + 1, l, mid, i, val);
	upd(x * 2 + 2, mid + 1, r, i, val);
	tour[x] = add(tour[x * 2 + 1], tour[x * 2 + 2]);
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n;
	unordered_map<int, int> um;
	vector<int> cmp;
	for(int i = 0; i < n; ++i){
		cin >> a[i] >> b[i];
		for(int j = b[i]; j >= a[i]; --j){
			v.push_back(j);
			cmp.push_back(j);
		}
	}
	
	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
	
	for(int i = 0; i < (int)cmp.size(); ++i) um[cmp[i]] = i;
	n = (int)v.size();
	
	for(int i = 0; i < n; ++i) v[i] = um[v[i]];

	for(int i = 0; i < n; ++i){
		int x = f(0, 0, n - 1, 0, v[i]);
		upd(0, 0, n - 1, v[i], add(x, 1));
	}
	
	cout << tour[0];
	
	return 0;
}

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