Submission #954331

#	Time	Username	Problem	Language	Result	Execution time	Memory
954331		Trisanu_Das	Sequence (APIO23_sequence)	C++17	47 / 100	339 ms	39344 KiB

sequence

#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T& container, char separator = ' ', char finish = '\n'){
        for(auto item: container) cout << item << separator;
        cout << finish;
    }
 
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
 
 
namespace Sub4{
    const int INF = 1e9 + 69;
    struct FenwickTree{
        int n;
        vector<int> a;
 
        FenwickTree(int _n){
            n = _n;
            a.resize(n+1, INF);
        }
 
        void update(int i, int v){
            for(; i <= n; i += (i & -i)) minimize(a[i], v);
        }
 
        int get(int i){
            int ans = INF;
            for(; i > 0; i -= (i & -i)) minimize(ans, a[i]);
            return ans;
        }
    };
 
    bool check(vector<int> a){
        for(int i: a) if (i > 3) return 0;
        return 1;
    }
 
    int edging(int n, vector<int> a){
        int ans = 0;
        vector<array<int, 3>> pref(n+1, {{0, n+1, n+1}});
        a.insert(a.begin(), -1);
        for(int i = 1; i<=n; ++i){
            pref[i] = pref[i-1];
            if (a[i] == 1) pref[i][0]++; 
            if (a[i] < 1) pref[i][1]--;
            else pref[i][1]++;
            if (a[i] <= 1) pref[i][2]++;
            else pref[i][2]--;
        }
 
        sort(pref.begin(), pref.end(), [] (array<int, 3> a, array<int, 3> b){
            if (a[2] != b[2]) return a[2] < b[2];
            return a[1] < b[1];
        });
 
        FenwickTree bit(n * 2 + 2);
        for(auto i: pref){
            maximize(ans, i[0] - bit.get(i[1] - 1));
            bit.update(i[1], i[0]);
        }
        return ans;
    }
 
    int solve(int n, vector<int> a){
        int ans = 0;
        for(int i = 1; i<=3; ++i){
            vector<int> b = a;
            for(int &j: b){
                if (j < i) j = 0;
                else if (j == i) j = 1;
                else j = 2;
            }
            maximize(ans, edging(n, b));
        }
 
        return ans;
    }
}
 
int sequence(int n, vector<int> a){
  if(n <= 2000){
    int occ[n + 1], ans = 0;
    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;
  }
  
  if(Sub4::check(a)) return Sub4::solve(n, a);
  
  int ans = 0;
  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]);
    ans = max(ans, p.second);
  }
  for(auto p : desc){
    auto p2 = lower_bound(a.begin(), a.end(), p.first) - a.begin();
    if(p2 >= n / 2) ans = max(ans, p.second + asc[p.first]);
    ans = max(ans, p.second);
  }
  return ans;
}

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