#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MOD = 1000000007;
set<pii> CH;
set<pii>::iterator get(int X) { return prev(CH.upper_bound({X, INF})); }
bool has(int X) {
auto it = CH.upper_bound({X, INF});
if(CH.begin() == it) return false;
int s, e; tie(s, e) = *prev(it);
return s <= X && X <= e && (s&1) == (X&1);
}
void push(int X) {
if(X < 1) return;
if(1 == X) X = 2;
if(!has(X)) {
if(has(X-1) && !has(X+1)) {
auto it = get(X-1);
int s, e; tie(s, e) = *it;
CH.erase(it); // TODO : erase
e -= 2;
if(s <= e) {
CH.insert({s, e}); // TODO : insert
}
push(X+1);
return;
}
if(!has(X-1) && has(X+1)) {
auto it = get(X+1);
int s, e; tie(s, e) = *it;
CH.erase(it); // TODO : erase
push(e+1);
return;
}
if(has(X-1) && has(X+1)) {
auto it = get(X);
int s, e; tie(s, e) = *it;
CH.erase(it); // TODO : erase
CH.insert({s, X-1}); // TODO : insert
push(e+1);
return;
}
CH.insert({X, X}); // TODO : insert
return;
}
auto it = get(X);
int s, e; tie(s, e) = *it;
CH.erase(it); // TODO : erase
if(s+1 < X) {
CH.insert({s+1, X-1}); // TODO : insert
}
push(e+1);
push(s-2);
}
int N;
ll getAns() {
vector<pii> V;
{
for(auto &v : CH) V.eb(v);
}
//for(auto &v : V) printf("(%d,%d) ", v.first, v.second); puts("");
vector<ll> DP[2];
int N = sz(V);
DP[0].resize(N); DP[1].resize(N);
if(1 < V[0].first-2) {
DP[0][0] = ll(V[0].first-4)/2 % MOD + 1;
}
DP[1][0] = 1 + ll(V[0].first-2)/2 * ((V[0].second-V[0].first)/2) % MOD;
for(int i = 1; i < N; i++) {
int l = V[i].first - V[i-1].second - 1;
int c = (V[i].second - V[i].first)/2;
DP[0][i] = (DP[1][i-1] * (l/2) % MOD) + (DP[0][i-1] * ((l+1)/2) % MOD);
DP[0][i] %= MOD;
DP[1][i] = DP[1][i-1] * (1 + (l/2) * c % MOD) % MOD;
DP[1][i] += DP[0][i-1] * (1 + ((l+1)/2) * c % MOD) % MOD;
DP[1][i] %= MOD;
}
//for(int i = 0; i < N; i++) printf("DP %d : %lld %lld\n", i, DP[0][i], DP[1][i]);
return (DP[0].back() + DP[1].back()) % MOD;
}
int main() {
cin >> N;
for(int i = 0; i < N; i++) {
int x;
cin >> x;
push(x+1);
cout << getAns() << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
735 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
735 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
735 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Execution timed out |
4085 ms |
1820 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
735 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
