Submission #970364

#	Time	Username	Problem	Language	Result	Execution time	Memory
970364		anton	Sequence (APIO23_sequence)	C++17	28 / 100	2079 ms	13468 KiB

sequence

#include "sequence.h"
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>

struct MD{
  priority_queue<int> l, r;
  void balance(){
    while(r.size()>l.size()){
      int v= -r.top();
      r.pop();
      l.push(v);
    }
    while(l.size()>r.size()+1){
      int v= l.top();
      l.pop();
      r.push(-v);
    }
  }
  void insert(int v){
    if(l.size() == 0 || v<=l.top()){
      l.push(v);
    }
    else{
      r.push(-v);
    }

    balance();
  }

  vector<int> medians(){
    vector<int> res;
    if(l.size()>r.size()){
      res.push_back(l.top());
    }
    else{
      res.push_back(l.top());
      res.push_back(-r.top());
    }
    return res;
  }
};

int sequence(int N, std::vector<int> A) {
  int res= 0;
  for(int i = 0; i<N; i++){
    vector<int> oc(N, 0);
    MD md;
    for(int j = i; j<N; j++){
      //cout<<i<<" "<<j<<endl;
      oc[A[j]-1]++;
      md.insert(A[j]-1);
      //cout<<"sz "<<md.l.size()<<" "<<md.r.size()<<endl;
      for(auto e: md.medians()){
        res= max(res, oc[e]);
        //cout<<e<<" "<<oc[e]<<endl;
      }
    }
  }
  return res;
}

• 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