oj.uz

Submission #984056

# Submission time Handle Problem Language Result Execution time Memory
984056 2024-05-16T09:42:24 Z hariaakas646 Sequence (APIO23_sequence) C++17
11 / 100
 2000 ms 123568 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;

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();
    int ma = 0;
    frange(i, n) {
    	forr(j, i, n) {
    		int l = j-i+1;
    		int lo = 1;
    		int hi = n;
    		while(lo != hi) {
    			int mid = (lo+hi)/2;
    			int c1 = tree.query(i, j, mid);
    			if(c1>=(l+1)/2) hi = mid;
    			else lo = mid+1;
    		}
    		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);
    		}

    		c2 = tree.query(i, j, lo+1);
    		c1 = tree.query(i, j, lo);
    		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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 5 ms 348 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 5 ms 348 KB Output is correct
13 Execution timed out 2043 ms 856 KB Time limit exceeded
14 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 Execution timed out 2085 ms 123568 KB Time limit exceeded
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 Execution timed out 2037 ms 123104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 123212 KB Time limit exceeded
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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 5 ms 348 KB Output is correct
13 Execution timed out 2043 ms 856 KB Time limit exceeded
14 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 5 ms 348 KB Output is correct
13 Execution timed out 2043 ms 856 KB Time limit exceeded
14 Halted 0 ms 0 KB -