Submission #985175

#	Time	Username	Problem	Language	Result	Execution time	Memory
985175		Tsagana	Sequence (APIO23_sequence)	C++17	0 / 100	412 ms	74652 KiB

sequence

  #include "sequence.h"

  //OP
#include <bits/stdc++.h>
 
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define pi pair<int, int >
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mset multiset
#define F first
#define S second
#define meta int M = (L + R) /2, x = 2 * id + 1, y = x + 1

using namespace std;

vector<int> ct[500005];
int N;

struct segTree {
  pi  seg[2000005];
  int lazy[2000005];
 
  void laze(int id, int l, int r) {
    if (!lazy[id]) {
      seg[id] = {seg[id].F + lazy[id], seg[id].S + lazy[id]};
      if (l != r) {
        lazy[id*2+1] += lazy[id];
        lazy[id*2+2] += lazy[id];
      }
      lazy[id] = 0;
    }
  }
 
  void build(int id, int L, int R, int val) {
    lazy[id] = 0;
    if (L == R) {seg[id].F = seg[id].S = val * (L); return;}
    meta;
    build(x, L, M, val);
    build(y, M + 1, R, val);
    seg[id].F = min(seg[x].F, seg[y].F);
    seg[id].S = max(seg[x].S, seg[y].S);
  } void build(int val) {build(0, 0, N, val);}
 
  void update(int id, int L, int R, int l, int r, int val) {
    if (L <= l && r >= R) lazy[id] += val;
    laze(id, L, R); meta;
    if (l > R || r < L || (l <= L && r >= R)) return;
    update(x, L, M, l, r, val);
    update(y, M + 1, R, l, r, val);
    seg[id].F = min(seg[x].F, seg[y].F);
    seg[id].S = max(seg[x].S, seg[y].S);
  } void update(int l, int r, int val) {update(0, 0, N, l + 1, r + 1, val);}
 
  pi query(int id, int L, int R, int l, int r) {
    laze(id, L, R); meta;
    if (l >  R || r <  L) return {(int)1e9, (int)-1e9};
    if (l <= L && r >= R) return seg[id];
    pi q1 = query(x, L, M, l, r);
    pi q2 = query(y, M + 1, R, l, r);
    return {min(q1.F, q2.F), max(q1.S, q2.S)};
  } pi query(int l, int r) {return query(0, 0, N, l + 1, r + 1);}
} les, mor;
 
int sequence(int n, vector<int> A) {
  N = n;
  for (int i = 0; i < N; i++) ct[A[i]].pb(i);
  int ans = 1;
  les.build(-1);
  mor.build(1);
  for (int i = 1; i <= N; i++) {
    for (int j: ct[i]) les.update(j, N-1, 2);
    for (int j = 0; j + ans < ct[i].size(); j++) {
      int st = ct[i][j];
      int en = ct[i][j+ans];
      int qles = les.query(en, N-1).S - les.query(-1, st-1).F;
      int qmor = mor.query(en, N-1).S - mor.query(-1, st-1).F;
      if  (qles >= 0 && qmor >= 0) {ans++; j--;}
    }
    for (int j: ct[i]) mor.update(j, N-1, -2);
  }
  return ans;
}
  //ED

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:78:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int j = 0; j + ans < ct[i].size(); j++) {
      |                     ~~~~~~~~^~~~~~~~~~~~~~

• 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