oj.uz

Submission #954291

# Submission time Handle Problem Language Result Execution time Memory
954291 2024-03-27T15:18:16 Z Trisanu_Das Sequence (APIO23_sequence) C++17
28 / 100
 373 ms 39496 KB 
#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
 
int sequence(int n, vector<int> a){
  int ans = 0;
  if(n <= 2000){
    int occ[n + 1];
    for(int i = 0; i < n; i++){
      memset(occ, 0, sizeof(occ));
      multiset<int> l, r;
      for(int j = i; j < n; j++){
        occ[a[j]]++;
        if(r.empty() || a[j] <= *r.begin()) l.insert(a[j]);
        else r.insert(a[j]);
 
        if(l.size() > r.size() + 1){
          r.insert(*--l.end());
          l.erase(--l.end());
        }
        if(r.size() > l.size()){
          l.insert(*r.begin());
          r.erase(r.begin());
        }
        ans = max(ans, occ[*--l.end()]);
        if(l.size() == r.size()) ans = max(ans, occ[*r.begin()]);
      }
    }
    return ans;
  }
  map<int, int> asc, desc;
  bool flag = true;
  for(int i = 0; i < n; i++){
    if(flag) asc[a[i]]++;
    else desc[a[i]]++;
    if(i && a[i] < a[i - 1]) flag = false;
  }
  sort(a.begin(), a.end());
  for(auto p : asc){
    auto p2 = lower_bound(a.begin(), a.end(), p.first) - a.begin();
    if(p2 >= n / 2) ans = max(ans, p.second + desc[p.first]);
  }
  for(auto p : desc){
    auto p2 = upper_bound(a.begin(), a.end(), p.first) - a.begin();
    if(p2 >= n / 2) ans = max(ans, p.second + asc[p.first]);
  }
  return ans;
}

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 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
17.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 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 243 ms 520 KB Output is correct
14 Correct 235 ms 348 KB Output is correct
15 Correct 241 ms 520 KB Output is correct
16 Correct 236 ms 524 KB Output is correct
17 Correct 281 ms 344 KB Output is correct
18 Correct 168 ms 348 KB Output is correct
19 Correct 257 ms 344 KB Output is correct
20 Correct 241 ms 592 KB Output is correct
21 Correct 244 ms 344 KB Output is correct
22 Correct 239 ms 348 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 203 ms 26956 KB Output is correct
3 Correct 200 ms 27972 KB Output is correct
4 Correct 39 ms 4176 KB Output is correct
5 Correct 204 ms 26840 KB Output is correct
6 Incorrect 176 ms 28752 KB Output isn't correct
7 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 Correct 44 ms 4424 KB Output is correct
3 Incorrect 52 ms 4172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 39416 KB Output is correct
2 Correct 338 ms 39496 KB Output is correct
3 Incorrect 344 ms 38612 KB Output isn't correct
4 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 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 243 ms 520 KB Output is correct
14 Correct 235 ms 348 KB Output is correct
15 Correct 241 ms 520 KB Output is correct
16 Correct 236 ms 524 KB Output is correct
17 Correct 281 ms 344 KB Output is correct
18 Correct 168 ms 348 KB Output is correct
19 Correct 257 ms 344 KB Output is correct
20 Correct 241 ms 592 KB Output is correct
21 Correct 244 ms 344 KB Output is correct
22 Correct 239 ms 348 KB Output is correct
23 Incorrect 35 ms 4436 KB Output isn't correct
24 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 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 243 ms 520 KB Output is correct
14 Correct 235 ms 348 KB Output is correct
15 Correct 241 ms 520 KB Output is correct
16 Correct 236 ms 524 KB Output is correct
17 Correct 281 ms 344 KB Output is correct
18 Correct 168 ms 348 KB Output is correct
19 Correct 257 ms 344 KB Output is correct
20 Correct 241 ms 592 KB Output is correct
21 Correct 244 ms 344 KB Output is correct
22 Correct 239 ms 348 KB Output is correct
23 Correct 203 ms 26956 KB Output is correct
24 Correct 200 ms 27972 KB Output is correct
25 Correct 39 ms 4176 KB Output is correct
26 Correct 204 ms 26840 KB Output is correct
27 Incorrect 176 ms 28752 KB Output isn't correct
28 Halted 0 ms 0 KB -