Submission #107758

#	Time	Username	Problem	Language	Result	Execution time	Memory
107758		Just_Solve_The_Problem	Boat (APIO16_boat)	C++11	31 / 100	2051 ms	470264 KiB

boat

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)507;
const int mod = (int)1e9 + 7; 

int add(int a, int b) {
	return (a + b) % mod;
}

int mul(int a, int b) {
	return (a * 1LL * b) % mod;
}

int siz = 1;

struct T {
	int l, r, val;
	T() {
		l = r = val = 0;
	}
}tree[(int)4e7];

void upd(int pos, int val, int v = 1, int l = 0, int r = 1e9) {
	if (l == r) {
		tree[v].val = add(tree[v].val, val);
		return ;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) {
		if (!tree[v].l) 
			tree[v].l = ++siz;
		upd(pos, val, tree[v].l, l, mid);
	} else {
		if (!tree[v].r) 
			tree[v].r = ++siz;
		upd(pos, val, tree[v].r, mid + 1, r);
	}
	tree[v].val = add(tree[tree[v].l].val, tree[tree[v].r].val);
}

int get(int l, int r, int v = 1, int tl = 0, int tr = 1e9) {
	if (tl > r || tr < l || v == 0) return 0;
	if (l <= tl && tr <= r) return tree[v].val;
	int mid = (tl + tr) >> 1;
	return add(get(l, r, tree[v].l, tl, mid), get(l, r, tree[v].r, mid + 1, tr));
}

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

main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &a[i], &b[i]);
	}
	upd(0, 1);
	for (int i = 1; i <= n; i++) {
		for (int j = b[i]; j >= a[i]; j--) {
			upd(j, get(0, j - 1));
		}
	}
	cout << add(get(0, 1e9), mod - 1);
}

Compilation message (stderr)

boat.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
boat.cpp: In function 'int main()':
boat.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
boat.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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