oj.uz

Submission #792912

# Submission time Handle Problem Language Result Execution time Memory
792912 2023-07-25T10:52:48 Z IvanJ Boat (APIO16_boat) C++17
9 / 100
 36 ms 340 KB 
#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 pot(int n, int k) {
	int ret = 1, pot = n;
	for(;k > 0;k >>= 1, pot = mult(pot, pot)) 
		if(k & 1) ret = mult(ret, pot);
	return ret;
}
int divide(int a, int b) {return mult(a, pot(b, MOD - 2));}
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;}

int n, m;
int a[maxn], b[maxn];
int dp[maxn * 3], pref[maxn * 3], sum[maxn * 3];

int main() {
	scanf("%d", &n);
	for(int i = 0;i < n;i++) 
		scanf("%d%d", a + i, b + i);
	
	set<int> s;
	s.insert(0), s.insert(1);
	for(int i = 0;i < n;i++) 
		s.insert(a[i]), s.insert(b[i]), s.insert(b[i] + 1);
	
	vector<int> v(all(s));
	m = (int)v.size();
	dp[0] = sum[0] = 1;
	for(int i = 0;i < m;i++) pref[i] = 1;
	
	for(int i = 0;i < n;i++) {
		int lo = 0, hi = 0;
		for(int j = 0;j < m;j++) {
			if(v[j] == a[i]) lo = j;
			if(v[j] == b[i]) hi = j;
		}
		
		for(int j = hi;j >= lo;j--) {
			int len = v[j + 1] - v[j];
			sum[j] = mult(pref[j - 1], len);
			sum[j] = add(sum[j], mult(divide(mult(len, len + 1), 2), dp[j]));
			dp[j] = add(dp[j], pref[j - 1]);
		}
	
		for(int j = 0;j < m;j++) {
			pref[j] = sum[j];
			if(j) pref[j] = add(pref[j], pref[j - 1]);
		}
	}
	printf("%d\n", sub(pref[m - 1], 1));
	return 0;
}

Compilation message

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 312 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 312 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Incorrect 36 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 312 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Incorrect 36 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -