#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;
inline void fuk() { puts("ERR!"); exit(-1); }
const int MOD = 1000000007;
struct MAT {
MAT(int a = 1, int b = 0, int c = 0, int d = 1)
: a(a), b(b), c(c), d(d) {}
// a b
// c d
int a, b, c, d;
void init() { a = d = 1; b = c = 0; }
MAT operator * (const MAT &t) const {
return MAT((ll(a)*t.a + ll(b)*t.c)%MOD, (ll(a)*t.b + ll(b)*t.d)%MOD
, (ll(c)*t.a + ll(d)*t.c)%MOD, (ll(c)*t.b + ll(d)*t.d)%MOD);
}
//void prt() { printf("[%d/%d/%d/%d] ", a, b, c, d); }
};
const int MAXN = 100005;
const int SQRN = 450;
struct BUK {
MAT mat[SQRN*2+5], matProd;
int S[SQRN*2+5], E[SQRN*2+5];
int n;
void init() { n = 0; matProd.init(); }
static void cal(MAT &mat, int ps, int pe, int s, int e) {
if(ps < 0) { mat.init(); return; }
int l = s-pe-1, c = (e-s)>>1;
//printf("CAL ps=%d, pe=%d, s=%d, e=%d :: l=%d, c=%d : ", ps, pe, s, e, l, c);
mat.a = (l+1)>>1; mat.b = l>>1;
mat.c = (ll(c)*((l+1)>>1) + 1) % MOD;
mat.d = (ll(c)*(l>>1) + 1) % MOD;
//mat.prt(); puts("");
}
void calAll() {
matProd.init();
for(int i = 0; i < n; i++)
matProd = mat[i] * matProd;
}
int find(int X) {
if(!n || X < S[0] || E[n-1] < X) return -1;
int i = 0; for(; i < n && S[i] < X; i++);
return i;
}
void push(int s, int e) {
int i = 0; for(; i < n && S[i] < s; i++);
if(!i || i == n) fuk(); // TODO
for(int j = n; i < j; j--) {
swap(mat[j-1], mat[j]);
S[j] = S[j-1];
E[j] = E[j-1];
}
S[i] = s; E[i] = e; n++;
cal(mat[i], S[i-1], E[i-1], s, e);
cal(mat[i+1], s, e, S[i+1], E[i+1]);
}
void pushFront(int ps, int pe, int s, int e) {
if(!n) fuk(); // TODO
//printf("PUSHFRONT %d %d / %d %d\n", ps, pe, s, e);
for(int i = n; i; i--) {
swap(mat[i-1], mat[i]);
S[i] = S[i-1];
E[i] = E[i-1];
}
S[0] = s; E[0] = e; n++;
cal(mat[0], ps, pe, s, e);
cal(mat[1], s, e, S[1], E[1]);
}
void pushBack(int s, int e) {
if(!n) fuk(); // TODO
S[n] = s; E[n] = e;
cal(mat[n], S[n-1], E[n-1], s, e);
n++;
}
void pushNew(int ps, int pe, int s, int e) {
S[0] = s; E[0] = e; n = 1;
cal(mat[0], ps, pe, s, e);
}
void pop(int ps, int pe, int i) {
//printf("POP %d %d %d\n", ps, pe, i);
cal(mat[i+1], ps, pe, S[i+1], E[i+1]);
for(int j = i+1; j < n; j++) {
swap(mat[j-1], mat[j]);
S[j-1] = S[j];
E[j-1] = E[j];
}
n--;
}
};
struct TBL {
BUK buk[SQRN+5];
MAT mat[MAXN*2];
int S[MAXN*2], E[MAXN*2];
int n, qn;
void release() {
n = qn = 0;
for(int i = 0; i < SQRN+5; i++) {
for(int j = 0; j < buk[i].n; j++) {
mat[n] = buk[i].mat[j];
S[n] = buk[i].S[j];
E[n] = buk[i].E[j];
n++;
}
buk[i].init();
}
for(int s = 0, e, i = 0;;) {
e = s+SQRN-1;
if(n <= e) e = n-1;
if(s > e) break;
buk[i].n = e-s+1;
for(int j = s, c = 0; j <= e; j++) {
buk[i].mat[c] = mat[j];
buk[i].S[c] = S[j];
buk[i].E[c] = E[j];
c++;
}
buk[i].calAll();
s = e+1; i++;
}
}
int findNxt(int i) {
for(i++; i < SQRN+5 && !buk[i].n; i++);
return SQRN+5 <= i ? -1 : i;
}
int findPrev(int i) {
for(i--; 0 <= i && !buk[i].n; i--);
return i;
}
void findPrev(int i, int j, int &ps, int &pe) {
//printf("findPrev %d %d\n", i, j);
if(j) {
ps = buk[i].S[j-1];
pe = buk[i].E[j-1];
return;
}
i = findPrev(i);
if(0 <= i) {
ps = buk[i].S[buk[i].n-1];
pe = buk[i].E[buk[i].n-1];
return;
}
ps = pe = -1;
}
void _push(int s, int e) {
int i = 0;
for(; i < SQRN+5 && buk[i].n && buk[i].E[buk[i].n-1] < s; i++);
if(SQRN+3 < i) {
i = SQRN+3;
if(!buk[i].n) {
int ps, pe; findPrev(i, 0, ps, pe);
buk[i].pushNew(ps, pe, s, e);
buk[i].calAll();
return;
}
buk[i].pushBack(s, e);
buk[i].calAll();
return;
}
//printf("PUSH %d %d / %d\n", s, e, i);
if(!buk[i].n) {
int ps, pe; findPrev(i, 0, ps, pe);
buk[i].pushNew(ps, pe, s, e);
buk[i].calAll();
int nxt = findNxt(i);
if(0 <= nxt) {
BUK::cal(buk[nxt].mat[0], s, e, buk[nxt].S[0], buk[nxt].E[0]);
buk[nxt].calAll();
}
return;
}
if(buk[i].n < 2 || e < buk[i].S[0]) {
int ps, pe; findPrev(i, 0, ps, pe);
buk[i].pushFront(ps, pe, s, e);
buk[i].calAll();
return;
}
buk[i].push(s, e);
buk[i].calAll();
}
void _pop(int s, int e) {
int i = 0, j = -1;
for(; i < SQRN+5; i++) {
j = buk[i].find(s);
if(0 <= j) break;
}
//if(j < 0) fuk(); // TODO
//printf("POP %d %d / %d %d | %d\n", s, e, i, j, buk[i].n);
if(buk[i].n-1 == j) {
int nxt = findNxt(i);
//printf("BACK %d\n", nxt);
int ps, pe; findPrev(i, j, ps, pe);
if(0 <= nxt) {
BUK::cal(buk[nxt].mat[0], ps, pe, buk[nxt].S[0], buk[nxt].E[0]);
buk[nxt].calAll();
}
buk[i].n--;
buk[i].calAll();
return;
}
int ps, pe; findPrev(i, j, ps, pe);
//printf("result ps=%d, pe=%d\n", ps, pe);
buk[i].pop(ps, pe, j);
buk[i].calAll();
}
void push(int s, int e) {
qn++;
_push(s, e);
if(SQRN == qn) release();
}
void pop(int s, int e) {
qn++;
_pop(s, e);
if(SQRN == qn) release();
}
/*
void prt() {
for(int i = 0; i <= 3; i++) {
printf("BUK %d : %d | ", i, buk[i].n);
for(int j = 0; j < buk[i].n; j++)
printf("(%d,%d) ", buk[i].S[j], buk[i].E[j]);
puts("");
for(int j = 0; j < buk[i].n; j++)
buk[i].mat[j].prt();
puts("");
}
puts("");
}
*/
MAT get() {
MAT ret;
for(int i = 0; i < SQRN+5; i++) if(buk[i].n) {
buk[i].calAll();
ret = buk[i].matProd * ret;
}
return ret;
}
} tbl;
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 insert(int s, int e) {
tbl.push(s, e);
CH.insert({s, e});
}
void erase(set<pii>::iterator it) {
tbl.pop(it->first, it->second);
CH.erase(it);
}
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;
erase(it);
e -= 2;
if(s <= e) insert(s, e);
push(X+1);
return;
}
if(!has(X-1) && has(X+1)) {
auto it = get(X+1);
int s, e; tie(s, e) = *it;
erase(it);
push(e+1);
return;
}
if(has(X-1) && has(X+1)) {
auto it = get(X);
int s, e; tie(s, e) = *it;
erase(it);
insert(s, X-1);
push(e+1);
return;
}
int s = X, e = X;
if(has(X-2)) {
auto it = get(X-2);
int p, q; tie(p, q) = *it;
erase(it);
s = p;
}
if(has(X+2)) {
auto it = get(X+2);
int p, q; tie(p, q) = *it;
erase(it);
e = q;
}
insert(s, e);
return;
}
auto it = get(X);
int s, e; tie(s, e) = *it;
erase(it);
if(s+1 < X) insert(s+1, X-1);
push(e+1);
push(s-2);
}
int N;
ll getAns() {
if(CH.empty()) return 0;
MAT mat = tbl.get();
int s, e; tie(s, e) = *CH.begin();
ll a = 0, b;
if(1 < s-2) a = (ll(s-4)/2 + 1) % MOD;
b = (1 + ll(s-2)/2 * ((e-s)/2)) % MOD;
//printf("getAns %d %d / %lld %lld\n", s, e, a, b);
ll ret = a*mat.a % MOD;
ret += b*mat.b % MOD;
ret += a*mat.c % MOD;
ret += b*mat.d % MOD;
return ret % MOD;
}
int main() {
ios::sync_with_stdio(false);
cin >> N;
for(int i = 0; i < N; i++) {
int x;
cin >> x;
push(x+1);
printf("%lld\n", getAns());
//tbl.prt();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 3 |
Correct |
11 ms |
11768 KB |
Output is correct |
| 4 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 5 |
Correct |
12 ms |
11812 KB |
Output is correct |
| 6 |
Correct |
11 ms |
11772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 3 |
Correct |
11 ms |
11768 KB |
Output is correct |
| 4 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 5 |
Correct |
12 ms |
11812 KB |
Output is correct |
| 6 |
Correct |
11 ms |
11772 KB |
Output is correct |
| 7 |
Correct |
11 ms |
11772 KB |
Output is correct |
| 8 |
Correct |
11 ms |
11768 KB |
Output is correct |
| 9 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 10 |
Correct |
12 ms |
11896 KB |
Output is correct |
| 11 |
Incorrect |
13 ms |
11768 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 3 |
Correct |
11 ms |
11768 KB |
Output is correct |
| 4 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 5 |
Correct |
12 ms |
11812 KB |
Output is correct |
| 6 |
Correct |
11 ms |
11772 KB |
Output is correct |
| 7 |
Correct |
11 ms |
11772 KB |
Output is correct |
| 8 |
Correct |
11 ms |
11768 KB |
Output is correct |
| 9 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 10 |
Correct |
12 ms |
11896 KB |
Output is correct |
| 11 |
Incorrect |
13 ms |
11768 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
11768 KB |
Output is correct |
| 2 |
Execution timed out |
4040 ms |
13632 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 3 |
Correct |
11 ms |
11768 KB |
Output is correct |
| 4 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 5 |
Correct |
12 ms |
11812 KB |
Output is correct |
| 6 |
Correct |
11 ms |
11772 KB |
Output is correct |
| 7 |
Correct |
11 ms |
11772 KB |
Output is correct |
| 8 |
Correct |
11 ms |
11768 KB |
Output is correct |
| 9 |
Correct |
12 ms |
11768 KB |
Output is correct |
| 10 |
Correct |
12 ms |
11896 KB |
Output is correct |
| 11 |
Incorrect |
13 ms |
11768 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
