Submission #792856

#	Time	Username	Problem	Language	Result	Execution time	Memory
792856		IvanJ	Boat (APIO16_boat)	C++17	31 / 100	2063 ms	49720 KiB

boat

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 505;
const int MOD = 1e9 + 7;

int mult(ll x, ll y) {return x * y % MOD;}
int add(int x, int y) {x += y;if(x >= MOD) x -= MOD;return x;}
int sub(int x, int y) {x -= y;if(x < 0) x += MOD;return x;}

struct Seg {
	int sz;
	vector<int> dp, L;
	vector<ii> nxt;
	
	void init() {
		sz = 1;
		dp.pb(0), L.pb(0);
		nxt.pb({-1, -1});
	}
	
	void expand(int x) {
		if(nxt[x].x == -1) {
			nxt[x].x = sz++;
			dp.pb(0), L.pb(0), nxt.pb({-1, -1});
		} 
		if(nxt[x].y == -1) {
			nxt[x].y = sz++;
			dp.pb(0), L.pb(0), nxt.pb({-1, -1});
		}
	}
	
	void prop(int x, int lo, int hi) {
		if(lo < hi) expand(x);
		dp[x] = add(dp[x], mult(L[x], hi - lo + 1));
		if(lo < hi) {
			L[nxt[x].x] = add(L[nxt[x].x], L[x]);
			L[nxt[x].y] = add(L[nxt[x].y], L[x]);
		}
		L[x] = 0;
	}
	
	int query(int x, int lo, int hi, int a, int b) {
		prop(x, lo, hi);
		if(hi < a || b < lo) return 0;
		if(a <= lo && hi <= b) return dp[x];
		int mid = (lo + hi) / 2;
		expand(x);
		int l = query(nxt[x].x, lo, mid, a, b);
		int r = query(nxt[x].y, mid + 1, hi, a, b);
		return add(l, r);
	}
	
	void update(int x, int lo, int hi, int a, int b, int v) {
		prop(x, lo, hi);
		if(hi < a || b < lo) return;
		if(a <= lo && hi <= b) {
			L[x] = add(L[x], v);
			prop(x, lo, hi);
			return;
		}
		int mid = (lo + hi) / 2;
		expand(x);
		update(nxt[x].x, lo, mid, a, b, v);
		update(nxt[x].y, mid + 1, hi, a, b, v);
		dp[x] = add(dp[nxt[x].x], dp[nxt[x].y]);
	}
	
	int get(int x) {return query(0, 0, 1e9, 0, x);}
	void upd(int lo, int hi, int v) {update(0, 0, 1e9, lo, hi, v);}
};

int n;
int a[maxn], b[maxn];

int main() {
	scanf("%d", &n);
	for(int i = 0;i < n;i++) 
		scanf("%d%d", a + i, b + i);
	
	Seg S;
	S.init();
	S.upd(0, 0, 1);
	S.upd(a[0], b[0], 1);

	for(int i = 1;i < n;i++) {
		for(int j = b[i];j >= a[i];j--)
			S.upd(j, j, S.get(j - 1));
	}
	
	int ans = S.get(1e9);
	ans = sub(ans, 1);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
boat.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d%d", a + i, b + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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