Submission #879434

#	Time	Username	Problem	Language	Result	Execution time	Memory
879434		rxlfd314	Sequence (APIO23_sequence)	C++17	12 / 100	170 ms	36944 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) (a = a > (b) ? a : (b))
#define chmin(a, b) (a = a < (b) ? a : (b))

struct BIT {
  vt<int> fen;
  BIT(int n) {
    fen.assign(n, 0);
  }
  void upd(int i, int v) {
    for (; i < size(fen); i += i+1 & -i-1)
      fen[i] += v;
  }
  int qry(int i) {
    int ret = 0;
    for (; ~i; i -= i+1 & -i-1)
      ret += fen[i];
    return ret;
  }
};

int sequence(int N, vt<int> A) {
  vt<int> inds[N];
  FOR(i, 0, N-1)
    inds[--A[i]].push_back(i);
  
  int ans = 0;
  BIT fen(N);
  FOR(ii, 0, N-1) {
    vt<ari3> v;
    FOR(i, 0, size(inds[ii])-1)
      v.push_back({2*i - inds[ii][i] + 2*fen.qry(inds[ii][i]), 2*fen.qry(inds[ii][i]) - inds[ii][i], i});
    sort(all(v));
    multiset<ari2> s;
    int j = 0;
    for (auto &[x, y, i] : v) {
      //cout << ii+1 << ": " << i << ' ' << x << ' ' << y << '\n';
      for (; j < size(v) && v[j][0] <= x + 1; j++) {
        auto it = s.insert({v[j][1], v[j][2]});
        if (next(it) != end(s) && (*next(it))[1] < v[j][2])
          s.erase(it);
        else
          while (it != begin(s) && (*prev(it))[1] > v[j][2])
            s.erase(prev(it));
      }
      auto it = s.lower_bound({y - 1, 0});
      /*
      for (auto &[a, b] : s)
        cout << '(' << a << ", " << b << ") ";
      cout << '\n';
      */
      if (it != end(s)) {
        chmax(ans, i - (*it)[1] + 1);
        //cout << ii+1 << ": " << inds[ii][(*it)[1]] << ' ' << inds[ii][i] << '\n';
      }
    }
    for (int i : inds[ii])
      fen.upd(i, 1);
  }
  
  return ans;
}

Compilation message (stderr)

sequence.cpp: In member function 'void BIT::upd(int, int)':
sequence.cpp:24:33: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   24 |     for (; i < size(fen); i += i+1 & -i-1)
      |                                ~^~
sequence.cpp: In member function 'int BIT::qry(int)':
sequence.cpp:29:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   29 |     for (; ~i; i -= i+1 & -i-1)
      |                     ~^~

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