Submission #761021

#	Time	Username	Problem	Language	Result	Execution time	Memory
761021		gun_gan	Sequence (APIO23_sequence)	C++17	0 / 100	37 ms	4184 KiB

sequence

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

const int MX = 5e5 + 5;
priority_queue<int> lf, rg;
int cnt[MX];

void insert(int x) {
      cnt[x]++;
      if(cnt[x] == 1) {
            lf.push(x);
            if(lf.size() >= rg.size()) {
                  int k = lf.top();
                  lf.pop();
                  rg.push(-k);
            }

            if(lf.size() && rg.size() && lf.top() > -rg.top()) {
                  int x = -rg.top();
                  rg.pop();
                  int y = lf.top();
                  lf.pop();

                  lf.push(x);
                  rg.push(-y);
            }
      }
}

int sequence(int N, vector<int> a) {
      bool S2 = 0, S3 = 1, S4 = 1;
      S2 &= N <= 2000;

      for(int i = 0; i < N; i++) {
            S4 &= a[i] <= 3;
      }

      int m = 0;
      for(int i = 0; i < N; i++) {
            if(a[i + 1] > a[i]) {
                  m = i;
                  for(int j = i + 1; j < N; j++) S3 &= a[j - 1] <= a[j];
                  break;
            }
      }

      if(S2) {
            int ans = 0;
            for(int i = 0; i < N; i++) {
                  for(int j = i; j < N; j++) {
                        insert(a[j]);
                        if(lf.size() == rg.size()) {
                              // cout << i << " " << j << " " << lf.top() << " " << -rg.top() << '\n';
                              ans = max(ans, cnt[lf.top()]);
                              ans = max(ans, cnt[-rg.top()]);
                        } else {
                              // cout << i << " " << j << " " << -rg.top() << '\n';
                              ans = max(ans, cnt[-rg.top()]);
                        }
                  }

                  for(int j = i; j < N; j++) cnt[a[j]]--;
                  while(lf.size()) lf.pop();
                  while(rg.size()) rg.pop();
            }

            return ans;
      }

      if(S3) {    
            int ans = 0;
            for(int i = 0; i <= m; i++) {
                  int j = i;
                  while(j + 1 <= m && a[j + 1] == a[i]) j++;
                  ans = max(ans, j - i + 1);
                  i = j;
            }

            for(int i = m + 1; i < N; i++) {
                  int j = i;
                  while(j + 1 < N && a[j + 1] == a[i]) j++;
                  ans = max(ans, j - i + 1);
                  i = j;
            }

            set<int> s, t;
            for(int i = 0; i < N; i++) {
                  cnt[a[i]]++;
                  s.insert(a[i]);
            }

            for(int i = m, j = m; i >= 0, j < N;) {
                  if(a[i] > a[j]) {
                        while(j + 1 < N && a[j] == a[j + 1]) j++;
                        t.insert(a[j]);
                        s.erase(a[j]);
                        j++;
                  } else if(a[i] < a[j]) {
                        while(i - 1 >= 0 && a[i - 1] == a[i]) i--;
                        t.insert(a[i]);
                        s.erase(a[i]);
                        i--;
                  } else {
                        int pi = i, pj = j;
                        s.erase(a[i]);
                        while(i - 1 >= 0 && a[i - 1] == a[i]) i--;
                        while(j + 1 < N && a[j] == a[j + 1]) j++;

                        if(abs((int)s.size() - (int)t.size()) <= 1) {
                              ans = max(ans, (pi - i + 1) + (pj - j + 1));
                        }

                        t.insert(a[i]);
                        i--, j++;
                  }
            }     

            return ans;
      }

      if(S4) {
            int lst[4] = {-1, -1, -1, -1};
            vector<array<int,3>> cnt(N);

            for(int i = 0; i < N; i++) {
                  if(i > 0) {
                        cnt[i][1] += cnt[i - 1][1];
                        cnt[i][2] += cnt[i - 1][2];
                        cnt[i][3] += cnt[i - 1][3];
                  }
                  cnt[i][a[i]]++;
            }

            int ans = cnt[N - 1][2];
            for(int i = 0; i < N; i++) {
                  int k = cnt[i][a[i]];
                  if(lst[a[i] ^ 2] != -1) k -= cnt[lst[a[i] ^ 2]][a[i]];
                  ans = max(ans, k);
                  lst[a[i]] = i;
            }

            return ans;
      }

      return -1;
}

// int main() {
      // cout << sequence(7, {1, 2, 3, 1, 2, 1, 3}) << '\n';
      // cout << sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1}) << '\n';
      // cout << sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2}) << '\n';
      // cout << sequence(7, {5, 4, 4, 2, 3, 4, 6}) << '\n';
// }

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:93:37: warning: left operand of comma operator has no effect [-Wunused-value]
   93 |             for(int i = m, j = m; i >= 0, j < N;) {
      |                                   ~~^~~~

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