# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
923228 |
2024-02-07T01:52:07 Z |
vjudge1 |
Boat (APIO16_boat) |
C++17 |
|
2000 ms |
17092 KB |
#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;
template<class A, class B>
bool maximize(A& x, B y) {
if (x < y) return x = y, true; else return false;
}
template<class A, class B>
bool minimize(A& x, B y) {
if (x > y) return x = y, true; else return false;
}
/* END OF TEMPLATE */
const int N = 5e2 + 7;
const int mod = 1e9 + 7;
int n, a[N], b[N];
void add(int& x, int y) {
if ((x+=y) >= mod) x-=mod;
}
namespace sub12 {
const int N = 1e6 + 5008;
struct BIT {
int bit[N], n;
BIT() {
n = 0;
REP(i, 0, N) bit[i] = 0;
}
void update(int p, int u) {
for (; p <= n; p+=p & -p) bit[p] = (bit[p] + u) % mod;
}
int Get(int p) {
int res = 0;
for (; p > 0; p-=p & -p) res = (res + bit[p]) % mod;
return res;
}
} bit;
int f[N], pre[N];
vector<int> E;
void buildE() {
FOR(i, 1, n)
FOR(j, a[i], b[i]) E.push_back(j);
sort(all(E));
vector<int> new_E;
for (auto x : E)
if (new_E.empty() || new_E.back() != x) new_E.push_back(x);
E = new_E;
}
void Process() {
buildE();
bit.n = (int)E.size();
int m = E.size();
FOR(i, 1, n) {
a[i] = lower_bound(all(E), a[i]) - E.begin() + 1;
b[i] = lower_bound(all(E), b[i]) - E.begin() + 1;
FOR(j, 0, m) f[j] = 0;
FOR(j, a[i], b[i]) add(f[j], pre[j - 1] + 1);
FOR(j, 1, m) add(f[j], f[j - 1]);
FOR(j, 0, m) add(pre[j], f[j]);
}
cout<<pre[m];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
ll sum = 0;
FOR(i, 1, n) {
cin>>a[i]>>b[i];
sum+=b[i] - a[i];
}
if (sum <= 1e6) {
sub12::Process();
return 0;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7772 KB |
Output is correct |
2 |
Correct |
3 ms |
7772 KB |
Output is correct |
3 |
Correct |
3 ms |
7768 KB |
Output is correct |
4 |
Correct |
3 ms |
7772 KB |
Output is correct |
5 |
Correct |
3 ms |
7988 KB |
Output is correct |
6 |
Correct |
3 ms |
7772 KB |
Output is correct |
7 |
Correct |
3 ms |
7988 KB |
Output is correct |
8 |
Correct |
3 ms |
7768 KB |
Output is correct |
9 |
Correct |
3 ms |
7772 KB |
Output is correct |
10 |
Correct |
3 ms |
7772 KB |
Output is correct |
11 |
Correct |
3 ms |
7768 KB |
Output is correct |
12 |
Correct |
3 ms |
7768 KB |
Output is correct |
13 |
Correct |
3 ms |
7772 KB |
Output is correct |
14 |
Correct |
3 ms |
7860 KB |
Output is correct |
15 |
Correct |
3 ms |
7772 KB |
Output is correct |
16 |
Correct |
2 ms |
7772 KB |
Output is correct |
17 |
Correct |
2 ms |
7768 KB |
Output is correct |
18 |
Correct |
2 ms |
7772 KB |
Output is correct |
19 |
Correct |
2 ms |
7872 KB |
Output is correct |
20 |
Correct |
2 ms |
7772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7772 KB |
Output is correct |
2 |
Correct |
3 ms |
7772 KB |
Output is correct |
3 |
Correct |
3 ms |
7768 KB |
Output is correct |
4 |
Correct |
3 ms |
7772 KB |
Output is correct |
5 |
Correct |
3 ms |
7988 KB |
Output is correct |
6 |
Correct |
3 ms |
7772 KB |
Output is correct |
7 |
Correct |
3 ms |
7988 KB |
Output is correct |
8 |
Correct |
3 ms |
7768 KB |
Output is correct |
9 |
Correct |
3 ms |
7772 KB |
Output is correct |
10 |
Correct |
3 ms |
7772 KB |
Output is correct |
11 |
Correct |
3 ms |
7768 KB |
Output is correct |
12 |
Correct |
3 ms |
7768 KB |
Output is correct |
13 |
Correct |
3 ms |
7772 KB |
Output is correct |
14 |
Correct |
3 ms |
7860 KB |
Output is correct |
15 |
Correct |
3 ms |
7772 KB |
Output is correct |
16 |
Correct |
2 ms |
7772 KB |
Output is correct |
17 |
Correct |
2 ms |
7768 KB |
Output is correct |
18 |
Correct |
2 ms |
7772 KB |
Output is correct |
19 |
Correct |
2 ms |
7872 KB |
Output is correct |
20 |
Correct |
2 ms |
7772 KB |
Output is correct |
21 |
Correct |
47 ms |
11456 KB |
Output is correct |
22 |
Correct |
41 ms |
11732 KB |
Output is correct |
23 |
Correct |
39 ms |
11216 KB |
Output is correct |
24 |
Correct |
42 ms |
11984 KB |
Output is correct |
25 |
Correct |
42 ms |
11456 KB |
Output is correct |
26 |
Correct |
41 ms |
11716 KB |
Output is correct |
27 |
Correct |
41 ms |
11728 KB |
Output is correct |
28 |
Correct |
40 ms |
11728 KB |
Output is correct |
29 |
Correct |
47 ms |
12164 KB |
Output is correct |
30 |
Execution timed out |
2037 ms |
17092 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
5724 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7772 KB |
Output is correct |
2 |
Correct |
3 ms |
7772 KB |
Output is correct |
3 |
Correct |
3 ms |
7768 KB |
Output is correct |
4 |
Correct |
3 ms |
7772 KB |
Output is correct |
5 |
Correct |
3 ms |
7988 KB |
Output is correct |
6 |
Correct |
3 ms |
7772 KB |
Output is correct |
7 |
Correct |
3 ms |
7988 KB |
Output is correct |
8 |
Correct |
3 ms |
7768 KB |
Output is correct |
9 |
Correct |
3 ms |
7772 KB |
Output is correct |
10 |
Correct |
3 ms |
7772 KB |
Output is correct |
11 |
Correct |
3 ms |
7768 KB |
Output is correct |
12 |
Correct |
3 ms |
7768 KB |
Output is correct |
13 |
Correct |
3 ms |
7772 KB |
Output is correct |
14 |
Correct |
3 ms |
7860 KB |
Output is correct |
15 |
Correct |
3 ms |
7772 KB |
Output is correct |
16 |
Correct |
2 ms |
7772 KB |
Output is correct |
17 |
Correct |
2 ms |
7768 KB |
Output is correct |
18 |
Correct |
2 ms |
7772 KB |
Output is correct |
19 |
Correct |
2 ms |
7872 KB |
Output is correct |
20 |
Correct |
2 ms |
7772 KB |
Output is correct |
21 |
Correct |
47 ms |
11456 KB |
Output is correct |
22 |
Correct |
41 ms |
11732 KB |
Output is correct |
23 |
Correct |
39 ms |
11216 KB |
Output is correct |
24 |
Correct |
42 ms |
11984 KB |
Output is correct |
25 |
Correct |
42 ms |
11456 KB |
Output is correct |
26 |
Correct |
41 ms |
11716 KB |
Output is correct |
27 |
Correct |
41 ms |
11728 KB |
Output is correct |
28 |
Correct |
40 ms |
11728 KB |
Output is correct |
29 |
Correct |
47 ms |
12164 KB |
Output is correct |
30 |
Execution timed out |
2037 ms |
17092 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |