oj.uz

Submission #388555

# Submission time Handle Problem Language Result Execution time Memory
388555 2021-04-12T05:19:18 Z talant117408 Boat (APIO16_boat) C++17
31 / 100
 1058 ms 135296 KB 
/*
    Code written by Talant I.D.
*/
#include <bits/stdc++.h>
 
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
 
const int mod = 1e9+7;
 
ll mode(ll a) {
    a %= mod;
    if (a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b) {
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b) {
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b) {
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 503;
int a[N], b[N], n;

bool subtask1() {
	int flag = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] == b[i]) flag++;
	}
	return flag == n;
}

bool subtask2() {
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		sum += b[i]-a[i];
	}
	return sum <= 1e6;
}

struct node {
	ll val;
	int lson, rson;
	node() {
		val = 0;
		lson = rson = -1;
	}
} tree[8000007];

int vertices = 1;

void create_lson(int v) {
	if (tree[v].lson == -1) {
		tree[v].lson = ++vertices;
	}
}

void create_rson(int v) {
	if (tree[v].rson == -1) {
		tree[v].rson = ++vertices;
	}
}

void update(int v, int l, int r, int pos, ll val) {
	if (l == r) {
		tree[v].val = add(tree[v].val, val);
		return;
	}
	int mid = (l+r) >> 1;
	create_lson(v);
	create_rson(v);
	if (pos <= mid) update(tree[v].lson, l, mid, pos, val);
	else update(tree[v].rson, mid+1, r, pos, val);
	tree[v].val = add(tree[tree[v].lson].val, tree[tree[v].rson].val);
}

ll get(int v, int l, int r, int ql, int qr) {
	if (l > qr || ql > r) return 0;
	if (ql <= l && r <= qr) return tree[v].val;
	int mid = (l+r) >> 1;
	create_lson(v);
	create_rson(v);
	return add(get(tree[v].lson, l, mid, ql, qr), get(tree[v].rson, mid+1, r, ql, qr));
}

int main() {
	do_not_disturb
	
    cin >> n;
    for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
	}
	
	if (subtask1()) {
		vector <ll> dp(n+1);
		dp[0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = i-1; j >= 0; j--) {
				if (a[i] > a[j]) {
					dp[i] = add(dp[i], dp[j]);
				}
			}
		}
		ll ans = 0;
		for (int i = 1; i <= n; i++) {
			ans = add(ans, dp[i]);
		}
		cout << ans << endl;
		return 0;
	}
	else if (subtask2()) {
		vector <vector <ll>> dp(n+1);
		dp[0].pb(1);
		update(1, 0, 1e9, 0, 1);
		ll ans = 0;
		
		for (int i = 1; i <= n; i++) {
			for (int j = a[i]; j <= b[i]; j++) {
				dp[i].pb(get(1, 0, 1e9, 0, j-1));
			}
			for (int j = a[i]; j <= b[i]; j++) {
				update(1, 0, 1e9, j, dp[i][j-a[i]]);
			}
		}
		
		for (int i = 1; i <= n; i++) {
			for (auto to : dp[i]) ans = add(ans, to);
		}
		
		cout << ans << endl;
		return 0;
	}
	
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125492 KB Output is correct
2 Correct 62 ms 125536 KB Output is correct
3 Correct 63 ms 125548 KB Output is correct
4 Correct 62 ms 125508 KB Output is correct
5 Correct 61 ms 125508 KB Output is correct
6 Correct 63 ms 125536 KB Output is correct
7 Correct 64 ms 125468 KB Output is correct
8 Correct 62 ms 125524 KB Output is correct
9 Correct 62 ms 125508 KB Output is correct
10 Correct 70 ms 125524 KB Output is correct
11 Correct 64 ms 125536 KB Output is correct
12 Correct 68 ms 125528 KB Output is correct
13 Correct 61 ms 125536 KB Output is correct
14 Correct 62 ms 125472 KB Output is correct
15 Correct 64 ms 125472 KB Output is correct
16 Correct 62 ms 125464 KB Output is correct
17 Correct 66 ms 125544 KB Output is correct
18 Correct 70 ms 125504 KB Output is correct
19 Correct 63 ms 125508 KB Output is correct
20 Correct 61 ms 125508 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125492 KB Output is correct
2 Correct 62 ms 125536 KB Output is correct
3 Correct 63 ms 125548 KB Output is correct
4 Correct 62 ms 125508 KB Output is correct
5 Correct 61 ms 125508 KB Output is correct
6 Correct 63 ms 125536 KB Output is correct
7 Correct 64 ms 125468 KB Output is correct
8 Correct 62 ms 125524 KB Output is correct
9 Correct 62 ms 125508 KB Output is correct
10 Correct 70 ms 125524 KB Output is correct
11 Correct 64 ms 125536 KB Output is correct
12 Correct 68 ms 125528 KB Output is correct
13 Correct 61 ms 125536 KB Output is correct
14 Correct 62 ms 125472 KB Output is correct
15 Correct 64 ms 125472 KB Output is correct
16 Correct 62 ms 125464 KB Output is correct
17 Correct 66 ms 125544 KB Output is correct
18 Correct 70 ms 125504 KB Output is correct
19 Correct 63 ms 125508 KB Output is correct
20 Correct 61 ms 125508 KB Output is correct
21 Correct 923 ms 134144 KB Output is correct
22 Correct 922 ms 134028 KB Output is correct
23 Correct 902 ms 133648 KB Output is correct
24 Correct 949 ms 134248 KB Output is correct
25 Correct 959 ms 134468 KB Output is correct
26 Correct 998 ms 133560 KB Output is correct
27 Correct 1050 ms 133588 KB Output is correct
28 Correct 1016 ms 133576 KB Output is correct
29 Correct 1028 ms 133536 KB Output is correct
30 Correct 1054 ms 135204 KB Output is correct
31 Correct 1036 ms 135296 KB Output is correct
32 Correct 1040 ms 135240 KB Output is correct
33 Correct 1016 ms 134816 KB Output is correct
34 Correct 1025 ms 135084 KB Output is correct
35 Correct 984 ms 134520 KB Output is correct
36 Correct 1035 ms 134932 KB Output is correct
37 Correct 1058 ms 135040 KB Output is correct
38 Correct 1027 ms 134940 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 125508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125492 KB Output is correct
2 Correct 62 ms 125536 KB Output is correct
3 Correct 63 ms 125548 KB Output is correct
4 Correct 62 ms 125508 KB Output is correct
5 Correct 61 ms 125508 KB Output is correct
6 Correct 63 ms 125536 KB Output is correct
7 Correct 64 ms 125468 KB Output is correct
8 Correct 62 ms 125524 KB Output is correct
9 Correct 62 ms 125508 KB Output is correct
10 Correct 70 ms 125524 KB Output is correct
11 Correct 64 ms 125536 KB Output is correct
12 Correct 68 ms 125528 KB Output is correct
13 Correct 61 ms 125536 KB Output is correct
14 Correct 62 ms 125472 KB Output is correct
15 Correct 64 ms 125472 KB Output is correct
16 Correct 62 ms 125464 KB Output is correct
17 Correct 66 ms 125544 KB Output is correct
18 Correct 70 ms 125504 KB Output is correct
19 Correct 63 ms 125508 KB Output is correct
20 Correct 61 ms 125508 KB Output is correct
21 Correct 923 ms 134144 KB Output is correct
22 Correct 922 ms 134028 KB Output is correct
23 Correct 902 ms 133648 KB Output is correct
24 Correct 949 ms 134248 KB Output is correct
25 Correct 959 ms 134468 KB Output is correct
26 Correct 998 ms 133560 KB Output is correct
27 Correct 1050 ms 133588 KB Output is correct
28 Correct 1016 ms 133576 KB Output is correct
29 Correct 1028 ms 133536 KB Output is correct
30 Correct 1054 ms 135204 KB Output is correct
31 Correct 1036 ms 135296 KB Output is correct
32 Correct 1040 ms 135240 KB Output is correct
33 Correct 1016 ms 134816 KB Output is correct
34 Correct 1025 ms 135084 KB Output is correct
35 Correct 984 ms 134520 KB Output is correct
36 Correct 1035 ms 134932 KB Output is correct
37 Correct 1058 ms 135040 KB Output is correct
38 Correct 1027 ms 134940 KB Output is correct
39 Incorrect 61 ms 125508 KB Output isn't correct
40 Halted 0 ms 0 KB -