Submission #483470

#	Time	Username	Problem	Language	Result	Execution time	Memory
483470		macktvz	Zoltan (COCI16_zoltan)	C++17	0 / 140	98 ms	65540 KiB

zoltan

// 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 (stderr)

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);
      |     ~~~~~~^~~~~~~

• Subtask 1: 0 / 140