// meta: found what strings are possible
// can have the string, the reverse string, and reverse some subsequence of the string that must include 1 and concatenate it to the rest
// can turn a strictly decreasing subsequence into a strictly increasing subsequence
// if we have a dec subs with the smallest two elements, should always take those
// two seg trees,
// iterate over the end of strictly decreasing subsequences, sum over all increasing subsequences in the rest that start with a greater number than it ends with
// longest subsequnce given that we have to start or end with this guy
// longest given that we have to end with this guy is the longest increasing subsequence of the rest of the array in reverse + the beginning of the array
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
struct Segment {
long long ways,num;
};
Segment join(Segment A, Segment B) {
Segment ret;
ret.num = max(A.num,B.num);
if (B.num > A.num) swap(A,B);
ret.ways = A.ways + (B.num == A.num ? B.ways : 0);
return ret;
}
Segment id;
template<class T> struct Seg { // comb(ID,b) = b
const T ID = id; T comb(T a, T b) { return join(a,b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n,ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // min on interval [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
Seg<Segment> f;
Seg<Segment> b;
// need to know beginning of decreasing sequence, beginning of increasing sequence
const int mod = 1e9+7;
int main() {
id.num = 0;
id.ways = 0;
int n; cin >> n;
vector<int> A(n);
int mxi;
int mxl = 0;
long long curr;
for (int &a : A) {
cin >> a;
mxi = max(mxi,a);
}
f.init(mxi+1);
b.init(mxi+1);
Segment r,l;
for(int i = n-1; i >= 0; i--) {
r = b.query(1,A[i]-1);
l = f.query(A[i]+1,mxi);
r.num++;l.num++;
if (r.ways == 0) r.ways = 1;
if (l.ways == 0) l.ways = 1;
r.ways %= mod; l.ways %= mod;
if (r.num+l.num-1 > mxl) {
mxl = r.num+l.num-1;
curr = (r.ways*l.ways)%mod;
} else if (r.num+l.num-1 == mxl) {
curr += (r.ways*l.ways)%mod;
curr %= mod;
}
b.upd(A[i],r);
f.upd(A[i],l);
}
for(int i = 0; i < n-mxl; i++) {
curr*=2;
curr %= mod;
}
cout << mxl << " " << curr << endl;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:79:18: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
79 | curr += (r.ways*l.ways)%mod;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:65:11: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
65 | f.init(mxi+1);
| ~~~~~~^~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
30 ms |
65540 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
31 ms |
65540 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
| 8 |
Runtime error |
4 ms |
460 KB |
Execution killed with signal 6 |
| 9 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
52 ms |
2952 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
44 ms |
2592 KB |
Execution killed with signal 6 |
| 13 |
Runtime error |
41 ms |
2548 KB |
Execution killed with signal 6 |
| 14 |
Runtime error |
52 ms |
2872 KB |
Execution killed with signal 6 |
| 15 |
Runtime error |
63 ms |
3524 KB |
Execution killed with signal 6 |
| 16 |
Runtime error |
75 ms |
3988 KB |
Execution killed with signal 6 |
| 17 |
Runtime error |
86 ms |
65540 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
91 ms |
65540 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
98 ms |
65540 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
82 ms |
65540 KB |
Execution killed with signal 9 |
