Submission #980958

#	Time	Username	Problem	Language	Result	Execution time	Memory
980958		nnin	Sequence (APIO23_sequence)	C++17	28 / 100	2045 ms	10248 KiB

sequence

#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;

int ct[500005];
priority_queue<int> le;
priority_queue<int, vector<int>, greater<int>> ri;

int sequence(int N, std::vector<int> A) {
  int ret = 0;
  for(int l=0;l<N;l++) {
    while(!le.empty()) ct[le.top()]--, le.pop();
    while(!ri.empty()) ct[ri.top()]--, ri.pop();
    for(int r=l;r<N;r++) {
      if(le.empty() || A[r]<=le.top()) le.push(A[r]);
      else ri.push(A[r]);
      if(le.size()>ri.size()+1) {
        ri.push(le.top());
        le.pop();
      }
      if(ri.size()>le.size()) {
        le.push(ri.top());
        ri.pop();
      }
      ct[A[r]]++;
      ret = max(ret, ct[le.top()]);
      if(le.size()==ri.size()) ret = max(ret, ct[ri.top()]);
    }
  }
  return ret;
}

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18