oj.uz

Submission #879434

# Submission time Handle Problem Language Result Execution time Memory
879434 2023-11-27T11:28:00 Z rxlfd314 Sequence (APIO23_sequence) C++17
12 / 100
 170 ms 36944 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 130 ms 31176 KB Output is correct
3 Incorrect 125 ms 31172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 148 ms 30564 KB Output is correct
3 Correct 145 ms 26972 KB Output is correct
4 Correct 144 ms 26836 KB Output is correct
5 Correct 113 ms 32088 KB Output is correct
6 Correct 162 ms 35640 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 36944 KB Output is correct
2 Correct 170 ms 36944 KB Output is correct
3 Incorrect 168 ms 36180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -