Submission #875950

#	Time	Username	Problem	Language	Result	Execution time	Memory
875950		Lobo	Boat (APIO16_boat)	C++17	31 / 100	2095 ms	191008 KiB

boat

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
const int maxn = 1e6+10;
const int maxv = 1e9;
const int lg = 31;
const int mod = 1e9+7;

int n;
int lc[maxn*lg], rc[maxn*lg], tr[maxn*lg], cntno;

int upd(int no, int l, int r, int pos, int val) {
	if(l > pos or r < pos) return no;
	if(no == 0) no = ++cntno;
	if(l == r) {
		tr[no]+= val;
		tr[no]%= mod;
		return no;
	}
	int mid = (l+r)/2;

	lc[no] = upd(lc[no],l,mid,pos,val);
	rc[no] = upd(rc[no],mid+1,r,pos,val);
	tr[no] = tr[lc[no]]+tr[rc[no]];
	tr[no]%= mod;
	return no;
}

int query(int no, int l, int r, int ll, int rr) {
	if(l > rr or r < ll or no == 0) return 0;
	if(l >= ll && r <= rr) return tr[no];
	int mid = (l+r)/2;
	return (query(lc[no],l,mid,ll,rr)+query(rc[no],mid+1,r,ll,rr))%mod;
}

int32_t main() {
	cin >> n;

	int rt = upd(0,0,maxv,0,1);
	for(int i = 1; i <= n; i++) {
		int a,b; cin >> a >> b;
		for(int j = b; j >= a; j--) {
			upd(rt,0,maxv,j,query(rt,0,maxv,0,j-1));
		}
	}

	cout << query(rt,0,maxv,1,maxv) << endl;
}

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