oj.uz

Submission #976286

# Submission time Handle Problem Language Result Execution time Memory
976286 2024-05-06T11:39:09 Z hocln Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 59224 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "sequence.h"
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
//const long long MOD = 1e9 + 7;
const long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first;
    return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto &i: v) os << i << ' ';
    return os;
}
int tc = 0;



int sequence(int n, vector<int>v) {
	int ans = 0;
	for(int i = 0;i < n;i++) { // i = L
		map<int,int>mp;
		Tree<pair<int,int>>st;
		int cnt = 0;
		for(int j = i;j < n;j++) { // j = R
			++mp[v[j]];
			st.insert({v[j],cnt++});
			chmax(ans, mp[st.find_by_order((j-i+1)/2)->first]);
			chmax(ans, mp[st.find_by_order((j-i)/2)->first]);
		}
	}
	return ans;
}
//inline void solve_test() {
	
//}

//int main()
//{
    ////srand(chrono::steady_clock::now().time_since_epoch().count());
    ////freopen("convention2.in", "r", stdin);
    ////freopen("convention2.out", "w", stdout);
	////cout << "Case #" << tc << ": " << ans << '\n';
	////cout << fixed << setprecision(7);
    ////ios::sync_with_stdio(0);
    ////cin.tie(0);cout.tie(0);
    ////int tt = 1;
    //////cin >> tt;
    ////while(tt--) {
		////++tc;
        ////solve_test();
    ////}
    //cout << sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2});
//}

Subtask #1
11.0 / 11.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 667 ms 620 KB Output is correct
14 Correct 661 ms 624 KB Output is correct
15 Correct 461 ms 592 KB Output is correct
16 Correct 445 ms 572 KB Output is correct
17 Correct 394 ms 556 KB Output is correct
18 Correct 565 ms 848 KB Output is correct
19 Correct 625 ms 612 KB Output is correct
20 Correct 618 ms 616 KB Output is correct
21 Correct 639 ms 608 KB Output is correct
22 Correct 644 ms 604 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2041 ms 50388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2058 ms 35432 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 2035 ms 59224 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 667 ms 620 KB Output is correct
14 Correct 661 ms 624 KB Output is correct
15 Correct 461 ms 592 KB Output is correct
16 Correct 445 ms 572 KB Output is correct
17 Correct 394 ms 556 KB Output is correct
18 Correct 565 ms 848 KB Output is correct
19 Correct 625 ms 612 KB Output is correct
20 Correct 618 ms 616 KB Output is correct
21 Correct 639 ms 608 KB Output is correct
22 Correct 644 ms 604 KB Output is correct
23 Execution timed out 2035 ms 8272 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 667 ms 620 KB Output is correct
14 Correct 661 ms 624 KB Output is correct
15 Correct 461 ms 592 KB Output is correct
16 Correct 445 ms 572 KB Output is correct
17 Correct 394 ms 556 KB Output is correct
18 Correct 565 ms 848 KB Output is correct
19 Correct 625 ms 612 KB Output is correct
20 Correct 618 ms 616 KB Output is correct
21 Correct 639 ms 608 KB Output is correct
22 Correct 644 ms 604 KB Output is correct
23 Execution timed out 2041 ms 50388 KB Time limit exceeded
24 Halted 0 ms 0 KB -