oj.uz

Submission #984073

# Submission time Handle Problem Language Result Execution time Memory
984073 2024-05-16T09:51:01 Z hariaakas646 Sequence (APIO23_sequence) C++17
11 / 100
 1660 ms 2097152 KB 
#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);
    		if(c1+1 <= (l+1)/2 && (l+1)/2<=c2) {
    			ma = max(ma, c2-c1);
    		}
    		lo = med[i][j].s;
    		c2 = tree.query(i, j, lo);
    		c1 = tree.query(i, j, lo-1);
    		if(c1+1 <= (l+1)/2 && (l+1)/2<=c2) {
    			ma = max(ma, c2-c1);
    		}    		
    	}
    }
    return ma;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 544 KB Output is correct

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 544 KB Output is correct
13 Correct 1653 ms 32276 KB Output is correct
14 Correct 1633 ms 32192 KB Output is correct
15 Correct 1587 ms 32192 KB Output is correct
16 Correct 1585 ms 32252 KB Output is correct
17 Correct 1550 ms 32268 KB Output is correct
18 Correct 1607 ms 32336 KB Output is correct
19 Correct 1654 ms 32212 KB Output is correct
20 Correct 1628 ms 32256 KB Output is correct
21 Incorrect 1660 ms 32208 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1309 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 891 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 949 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 544 KB Output is correct
13 Correct 1653 ms 32276 KB Output is correct
14 Correct 1633 ms 32192 KB Output is correct
15 Correct 1587 ms 32192 KB Output is correct
16 Correct 1585 ms 32252 KB Output is correct
17 Correct 1550 ms 32268 KB Output is correct
18 Correct 1607 ms 32336 KB Output is correct
19 Correct 1654 ms 32212 KB Output is correct
20 Correct 1628 ms 32256 KB Output is correct
21 Incorrect 1660 ms 32208 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 544 KB Output is correct
13 Correct 1653 ms 32276 KB Output is correct
14 Correct 1633 ms 32192 KB Output is correct
15 Correct 1587 ms 32192 KB Output is correct
16 Correct 1585 ms 32252 KB Output is correct
17 Correct 1550 ms 32268 KB Output is correct
18 Correct 1607 ms 32336 KB Output is correct
19 Correct 1654 ms 32212 KB Output is correct
20 Correct 1628 ms 32256 KB Output is correct
21 Incorrect 1660 ms 32208 KB Output isn't correct
22 Halted 0 ms 0 KB -