oj.uz

Submission #483470

# Submission time Handle Problem Language Result Execution time Memory
483470 2021-10-29T19:28:14 Z macktvz Zoltan (COCI16_zoltan) C++17
0 / 140
 98 ms 65540 KB 
// 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);
      |     ~~~~~~^~~~~~~

Subtask #1
0 / 140.0

# Verdict Execution time Memory 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