oj.uz

Submission #981983

# Submission time Handle Problem Language Result Execution time Memory
981983 2024-05-13T17:35:21 Z nnin Sequence (APIO23_sequence) C++17
41 / 100
 2000 ms 74836 KB 
#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
 
vector<int> ct[500005];
int N;
 
struct segTree {
  pii seg[4*500005];
  int lazy[4*500005];
 
  void laze(int i, int l, int r) {
    if(lazy[i]) {
      seg[i] = {seg[i].f+lazy[i], seg[i].s+lazy[i]};
      if(l!=r) {
        lazy[i*2+1] += lazy[i];
        lazy[i*2+2] += lazy[i];
      }
      lazy[i] = 0;
    }
  }
 
  void build(int i, int l, int r, int val) {
    lazy[i] = 0;
    if(l==r) {
      seg[i].f = seg[i].s = val*(l);
      return;
    }
    int m = (l+r)/2;
    build(i*2+1, l, m, val);
    build(i*2+2, m+1, r, val);
    seg[i].f = min(seg[i*2+1].f, seg[i*2+2].f);
    seg[i].s = max(seg[i*2+1].s, seg[i*2+2].s);
  }
  void build(int val) {
    build(0, 0, N, val);
  }
 
  void update(int i, int l, int r, int wl, int wr, int val) {
    if(wl<=l && wr>=r) lazy[i] += val;
    laze(i, l, r);
    if(wl>r || wr<l || (wl<=l && wr>=r)) return;
    int m = (l+r)/2;
    update(i*2+1, l, m, wl, wr, val);
    update(i*2+2, m+1, r, wl, wr, val);
    seg[i].f = min(seg[i*2+1].f, seg[i*2+2].f);
    seg[i].s = max(seg[i*2+1].s, seg[i*2+2].s);
  }
  void update(int wl, int wr, int val) {
    update(0, 0, N, wl+1, wr+1, val);
  }
 
  pii query(int i, int l, int r, int wl, int wr) {
    laze(i, l, r);
    if(wl>r || wr<l) return {(int)1e9, (int)-1e9};
    if(wl<=l && wr>=r) return seg[i];
    int m = (l+r)/2;
    pii q1 = query(i*2+1, l, m, wl, wr);
    pii q2 = query(i*2+2, m+1, r, wl, wr);
    return {min(q1.f, q2.f), max(q1.s, q2.s)};
  }
  pii query(int wl, int wr) {
    return query(0, 0, N, wl+1, wr+1);
  }
} les, mor;
 
bool check(int x) {
  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+x-1<ct[i].size();j++) {
      int st = ct[i][j];
      int en = ct[i][j+x-1];
      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) return true;
    }
    for(int j:ct[i]) {
      mor.update(j, N-1, -2);
    }
  }
  return false;
}
 
int sequence(int n, std::vector<int> A) {
  N = n;
  for(int i=0;i<N;i++) {
    ct[A[i]].push_back(i);
  }
  int l = 1, r = 1;
  for(int i=1;i<=N;i++) {
    r = max(r, (int)ct[i].size());
  }
  while(r>1) {
    if(check(r)) return r;
    r--;
  }
  return l;
}

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 46680 KB Output is correct
2 Correct 8 ms 46684 KB Output is correct
3 Correct 8 ms 46684 KB Output is correct
4 Correct 8 ms 46680 KB Output is correct
5 Correct 8 ms 46784 KB Output is correct
6 Correct 8 ms 46684 KB Output is correct
7 Correct 9 ms 46684 KB Output is correct
8 Correct 8 ms 46684 KB Output is correct
9 Correct 8 ms 46780 KB Output is correct
10 Correct 9 ms 46940 KB Output is correct
11 Correct 8 ms 46680 KB Output is correct
12 Correct 8 ms 46680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 46680 KB Output is correct
2 Correct 8 ms 46684 KB Output is correct
3 Correct 8 ms 46684 KB Output is correct
4 Correct 8 ms 46680 KB Output is correct
5 Correct 8 ms 46784 KB Output is correct
6 Correct 8 ms 46684 KB Output is correct
7 Correct 9 ms 46684 KB Output is correct
8 Correct 8 ms 46684 KB Output is correct
9 Correct 8 ms 46780 KB Output is correct
10 Correct 9 ms 46940 KB Output is correct
11 Correct 8 ms 46680 KB Output is correct
12 Correct 8 ms 46680 KB Output is correct
13 Correct 9 ms 46684 KB Output is correct
14 Correct 11 ms 46884 KB Output is correct
15 Correct 13 ms 46684 KB Output is correct
16 Correct 18 ms 46684 KB Output is correct
17 Correct 37 ms 46680 KB Output is correct
18 Correct 8 ms 46684 KB Output is correct
19 Correct 9 ms 46684 KB Output is correct
20 Correct 9 ms 46780 KB Output is correct
21 Correct 232 ms 46680 KB Output is correct
22 Correct 195 ms 46684 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 46680 KB Output is correct
2 Correct 83 ms 68880 KB Output is correct
3 Correct 291 ms 68748 KB Output is correct
4 Correct 222 ms 61016 KB Output is correct
5 Correct 292 ms 67744 KB Output is correct
6 Correct 129 ms 67724 KB Output is correct
7 Execution timed out 2049 ms 61340 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 46684 KB Output is correct
2 Correct 117 ms 61176 KB Output is correct
3 Execution timed out 2041 ms 60856 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 74604 KB Output is correct
2 Correct 465 ms 74836 KB Output is correct
3 Correct 139 ms 73992 KB Output is correct
4 Correct 139 ms 73884 KB Output is correct
5 Correct 261 ms 70688 KB Output is correct
6 Correct 415 ms 70592 KB Output is correct
7 Correct 376 ms 69496 KB Output is correct
8 Correct 250 ms 68944 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 46680 KB Output is correct
2 Correct 8 ms 46684 KB Output is correct
3 Correct 8 ms 46684 KB Output is correct
4 Correct 8 ms 46680 KB Output is correct
5 Correct 8 ms 46784 KB Output is correct
6 Correct 8 ms 46684 KB Output is correct
7 Correct 9 ms 46684 KB Output is correct
8 Correct 8 ms 46684 KB Output is correct
9 Correct 8 ms 46780 KB Output is correct
10 Correct 9 ms 46940 KB Output is correct
11 Correct 8 ms 46680 KB Output is correct
12 Correct 8 ms 46680 KB Output is correct
13 Correct 9 ms 46684 KB Output is correct
14 Correct 11 ms 46884 KB Output is correct
15 Correct 13 ms 46684 KB Output is correct
16 Correct 18 ms 46684 KB Output is correct
17 Correct 37 ms 46680 KB Output is correct
18 Correct 8 ms 46684 KB Output is correct
19 Correct 9 ms 46684 KB Output is correct
20 Correct 9 ms 46780 KB Output is correct
21 Correct 232 ms 46680 KB Output is correct
22 Correct 195 ms 46684 KB Output is correct
23 Correct 185 ms 53604 KB Output is correct
24 Correct 132 ms 53596 KB Output is correct
25 Correct 218 ms 53588 KB Output is correct
26 Correct 1140 ms 52560 KB Output is correct
27 Correct 454 ms 52312 KB Output is correct
28 Execution timed out 2025 ms 52568 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 46680 KB Output is correct
2 Correct 8 ms 46684 KB Output is correct
3 Correct 8 ms 46684 KB Output is correct
4 Correct 8 ms 46680 KB Output is correct
5 Correct 8 ms 46784 KB Output is correct
6 Correct 8 ms 46684 KB Output is correct
7 Correct 9 ms 46684 KB Output is correct
8 Correct 8 ms 46684 KB Output is correct
9 Correct 8 ms 46780 KB Output is correct
10 Correct 9 ms 46940 KB Output is correct
11 Correct 8 ms 46680 KB Output is correct
12 Correct 8 ms 46680 KB Output is correct
13 Correct 9 ms 46684 KB Output is correct
14 Correct 11 ms 46884 KB Output is correct
15 Correct 13 ms 46684 KB Output is correct
16 Correct 18 ms 46684 KB Output is correct
17 Correct 37 ms 46680 KB Output is correct
18 Correct 8 ms 46684 KB Output is correct
19 Correct 9 ms 46684 KB Output is correct
20 Correct 9 ms 46780 KB Output is correct
21 Correct 232 ms 46680 KB Output is correct
22 Correct 195 ms 46684 KB Output is correct
23 Correct 83 ms 68880 KB Output is correct
24 Correct 291 ms 68748 KB Output is correct
25 Correct 222 ms 61016 KB Output is correct
26 Correct 292 ms 67744 KB Output is correct
27 Correct 129 ms 67724 KB Output is correct
28 Execution timed out 2049 ms 61340 KB Time limit exceeded
29 Halted 0 ms 0 KB -