oj.uz

Submission #981638

# Submission time Handle Problem Language Result Execution time Memory
981638 2024-05-13T11:58:57 Z 8pete8 Sequence (APIO23_sequence) C++17
35 / 100
 218 ms 13776 KB 
#include "sequence.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int mxn=5e5,lg=24;
int mx=0;
struct fen{
  //using fenwick cus i dont wanna write slding median
  int fwk[mxn+10];
  vector<pii>keep;
  void update(int pos,int val){
    keep.pb({pos,val});
    for(int i=pos;i<=mx;i+=(i&-i))fwk[i]+=val;
  }
  int qry(int pos){
    if(pos<0)return 0;
    int sum=0;
    for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
    return sum;
  }
  void re(){
    for(auto i:keep)for(int j=i.f;j<=mx;j+=(j&-j))fwk[j]-=i.s;
    keep.clear();
  }
  int get(int x){
    x++;
    int pos=0,sum=0;
    for(int i=lg;i>=0;i--){
      if(pos+(1LL<<i)<=mx&&fwk[pos+(1LL<<i)]+sum<x){
        pos+=(1LL<<i);
        sum+=fwk[pos];
      }
    }
    return pos+1;
  }
}t;
int cnt[mxn+10],r[mxn+10],l[mxn+10];
int sequence(int n, vector<int>v){
  int ans=0;
  if(n>2e3){
    //sub 3 case get l,r or get l-> other side
    for(auto i:v)cnt[i]++,l[i]=n+1;
    for(int i=0;i<n;i++)r[v[i]]=max(r[v[i]],i),l[v[i]]=min(l[v[i]],i);
    for(int i=0;i<n;i++){
      int cur=i;
      while(cur<v.size()&&v[cur]==v[i])cur++;
      ans=max(ans,cur-i);//take range l,r
      i=cur-1;
    }
    for(auto i:v){//take l->r
      int other=n-(r[i]-l[i]+1);
      if(other+cnt[i]>=(n/2)+1)ans=max(ans,cnt[i]);
    }
    return ans;
  }
  for(auto i:v)mx=max(mx,i);
  auto bru=[&](int x){
    int a=t.get(x);
    return t.qry(a)-t.qry(a-1);
  };
  for(int i=0;i<n;i++){
    t.re();
    for(int j=i;j<n;j++){
      t.update(v[j],1);
      int x1=(j-i)/2,x2=ceil((j-i)*1.0/2*1.0);
      ans=max({ans,bru(x1),bru(x2)});
    }
  }
  if(ans==0)assert(0);
  return ans;
}
/*
int32_t main(){
  int n;cin>>n;
  vector<int>v(n);
  for(int i=0;i<n;i++)cin>>v[i];
  cout<<sequence(n,v);
}*/
/*
9
1 1 1 2 2 3 2 2 1
*/

/*
constraint of being a medain
A number of number <x,B number of number >x,C number of number ==x
if C>=A+B
if A+C>=B && C<=A+B
if A+B>=c && B<=A+C
i might be wrong
*/

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |       while(cur<v.size()&&v[cur]==v[i])cur++;
      |             ~~~^~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 177 ms 2396 KB Output is correct
14 Correct 205 ms 2512 KB Output is correct
15 Correct 119 ms 2516 KB Output is correct
16 Correct 120 ms 2516 KB Output is correct
17 Correct 96 ms 2396 KB Output is correct
18 Correct 218 ms 2396 KB Output is correct
19 Correct 170 ms 2392 KB Output is correct
20 Correct 150 ms 2396 KB Output is correct
21 Correct 174 ms 2392 KB Output is correct
22 Correct 176 ms 2396 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 42 ms 10576 KB Output is correct
3 Correct 43 ms 10576 KB Output is correct
4 Correct 34 ms 6224 KB Output is correct
5 Correct 42 ms 10580 KB Output is correct
6 Correct 42 ms 13776 KB Output is correct
7 Correct 36 ms 7760 KB Output is correct
8 Correct 39 ms 7760 KB Output is correct
9 Correct 35 ms 7508 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 36 ms 6256 KB Output is correct
3 Incorrect 36 ms 7376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 177 ms 2396 KB Output is correct
14 Correct 205 ms 2512 KB Output is correct
15 Correct 119 ms 2516 KB Output is correct
16 Correct 120 ms 2516 KB Output is correct
17 Correct 96 ms 2396 KB Output is correct
18 Correct 218 ms 2396 KB Output is correct
19 Correct 170 ms 2392 KB Output is correct
20 Correct 150 ms 2396 KB Output is correct
21 Correct 174 ms 2392 KB Output is correct
22 Correct 176 ms 2396 KB Output is correct
23 Incorrect 8 ms 5212 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 177 ms 2396 KB Output is correct
14 Correct 205 ms 2512 KB Output is correct
15 Correct 119 ms 2516 KB Output is correct
16 Correct 120 ms 2516 KB Output is correct
17 Correct 96 ms 2396 KB Output is correct
18 Correct 218 ms 2396 KB Output is correct
19 Correct 170 ms 2392 KB Output is correct
20 Correct 150 ms 2396 KB Output is correct
21 Correct 174 ms 2392 KB Output is correct
22 Correct 176 ms 2396 KB Output is correct
23 Correct 42 ms 10576 KB Output is correct
24 Correct 43 ms 10576 KB Output is correct
25 Correct 34 ms 6224 KB Output is correct
26 Correct 42 ms 10580 KB Output is correct
27 Correct 42 ms 13776 KB Output is correct
28 Correct 36 ms 7760 KB Output is correct
29 Correct 39 ms 7760 KB Output is correct
30 Correct 35 ms 7508 KB Output is correct
31 Correct 36 ms 6256 KB Output is correct
32 Incorrect 36 ms 7376 KB Output isn't correct
33 Halted 0 ms 0 KB -