oj.uz

Submission #984076

# Submission time Handle Problem Language Result Execution time Memory
984076 2024-05-16T09:54:19 Z hariaakas646 Sequence (APIO23_sequence) C++17
28 / 100
 1647 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);
    		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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 3 ms 348 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 536 KB Output is correct
12 Correct 3 ms 448 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 3 ms 348 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 536 KB Output is correct
12 Correct 3 ms 448 KB Output is correct
13 Correct 1632 ms 32272 KB Output is correct
14 Correct 1617 ms 32192 KB Output is correct
15 Correct 1551 ms 32192 KB Output is correct
16 Correct 1588 ms 32260 KB Output is correct
17 Correct 1566 ms 32264 KB Output is correct
18 Correct 1638 ms 32276 KB Output is correct
19 Correct 1626 ms 32212 KB Output is correct
20 Correct 1635 ms 32256 KB Output is correct
21 Correct 1647 ms 32336 KB Output is correct
22 Correct 1646 ms 32216 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1277 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 0 ms 348 KB Output is correct
2 Runtime error 888 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 1025 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 3 ms 348 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 536 KB Output is correct
12 Correct 3 ms 448 KB Output is correct
13 Correct 1632 ms 32272 KB Output is correct
14 Correct 1617 ms 32192 KB Output is correct
15 Correct 1551 ms 32192 KB Output is correct
16 Correct 1588 ms 32260 KB Output is correct
17 Correct 1566 ms 32264 KB Output is correct
18 Correct 1638 ms 32276 KB Output is correct
19 Correct 1626 ms 32212 KB Output is correct
20 Correct 1635 ms 32256 KB Output is correct
21 Correct 1647 ms 32336 KB Output is correct
22 Correct 1646 ms 32216 KB Output is correct
23 Runtime error 902 ms 2097152 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 3 ms 348 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 536 KB Output is correct
12 Correct 3 ms 448 KB Output is correct
13 Correct 1632 ms 32272 KB Output is correct
14 Correct 1617 ms 32192 KB Output is correct
15 Correct 1551 ms 32192 KB Output is correct
16 Correct 1588 ms 32260 KB Output is correct
17 Correct 1566 ms 32264 KB Output is correct
18 Correct 1638 ms 32276 KB Output is correct
19 Correct 1626 ms 32212 KB Output is correct
20 Correct 1635 ms 32256 KB Output is correct
21 Correct 1647 ms 32336 KB Output is correct
22 Correct 1646 ms 32216 KB Output is correct
23 Runtime error 1277 ms 2097152 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -