Submission #984076

#	Time	Username	Problem	Language	Result	Execution time	Memory
984076		hariaakas646	Sequence (APIO23_sequence)	C++17	28 / 100	1647 ms	2097152 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

typedef tree<
    int,
    null_type,
    less_equal<int>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;

template <class T>
struct SegTree
{
    int size = 1, n;
    vector<T> segtree;
    vector<T> vec;

    T def; // Assign a value

    void init(int l, T defv)
    {
        n = l;
        def = defv;

        while (size < n)
            size *= 2;

        segtree.assign(2 * size, def);
        vec.assign(size, def);
    }

    T operation(T x, T y)
    {
        T out;
        int i1 = 0;
        int i2 = 0;
        frange(i, int(x.size()+y.size())) {
        	if(i1 == (int)x.size()) {
        		out.pb(y[i2++]);
        	}
        	else if(i2 == (int)y.size()) {
        		out.pb(x[i1++]);
        	}
        	else if(x[i1] <= y[i2]) {
        		out.pb(x[i1++]);
        	}
        	else {
        		out.pb(y[i2++]);
        	}
        }
        return out;
    }

    void recalculate(int x)
    {
        segtree[x] = operation(segtree[2 * x + 1], segtree[2 * x + 2]);
    }

    void build(int x, int l, int r)
    {
        if (l == r)
        {
            segtree[x] = vec[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * x + 1, l, mid);
        build(2 * x + 2, mid + 1, r);
        recalculate(x);
    }

    void build()
    {
        build(0, 0, size - 1);
    }

    void set(int id, T val)
    {
        vec[id] = val;
    }

    int query(int x, int l, int r, int lx, int rx, int v)
    {
        if (lx > r || rx < l)
        {
            return 0;
        }
        if (lx <= l && r <= rx)
        {
            return upper_bound(all(segtree[x]), v) - segtree[x].begin();
        }
        int mid = (l + r) / 2;
        int v1 = query(2 * x + 1, l, mid, lx, rx, v);
        int v2 = query(2 * x + 2, mid + 1, r, lx, rx, v);
        return v1+v2;
    }

    int query(int lx, int rx, int v)
    {
        return query(0, 0, size - 1, lx, rx, v);
    }
};



int sequence(int n, std::vector<int> vec) {
    SegTree<vi> tree;
    tree.init(n, vi(0));
    frange(i, n) {
    	tree.set(i, {vec[i]});
    }
    tree.build();
    vector<vii> med(n, vii(n));
    ordered_set st;
    frange(i, n) {
    	st = {};
    	forr(j, i, n) {
    		st.insert(vec[j]);
    		int l = j-i+1;
    		med[i][j].f = *st.find_by_order((l-1)/2);
    		med[i][j].s = *st.find_by_order(l/2);
    	}
    }
    int ma = 0;
    frange(i, n) {
    	forr(j, i, n) {
    		int l = j-i+1;
    		int lo = med[i][j].f;
    		
    		int c2 = tree.query(i, j, lo);
    		int c1 = tree.query(i, j, lo-1);
    		// printf("%d %d %d %d %d\n", i, j, lo, c1, c2);
    		ma = max(ma, c2-c1);
    		
    		lo = med[i][j].s;
    		c2 = tree.query(i, j, lo);
    		c1 = tree.query(i, j, lo-1);
    		ma = max(ma, c2-c1);
    		    		
    	}
    }
    return ma;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:155:11: warning: unused variable 'l' [-Wunused-variable]
  155 |       int l = j-i+1;
      |           ^

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18