oj.uz

Submission #981620

# Submission time Handle Problem Language Result Execution time Memory
981620 2024-05-13T11:47:22 Z 8pete8 Sequence (APIO23_sequence) C++17
28 / 100
 217 ms 12100 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,inf=1e18,minf=-1e18;
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];
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]++;
    for(int i=0;i<n;i++)r[v[i]]=max(r[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
      
      //or we take here -> the other side
      int other=n-(r[v[i]]-i+1);//number of number <i
      //we can only do it if we can make the median <=x
      if(other+cnt[v[i]]<=(n/2)+1)ans=max(ans,cnt[v[i]]);
      i=cur-1;
    }
    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);
}*/
/*
7
1 2 3 1 2 1 3
*/

/*
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:38:29: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   38 | const int mxn=5e5,lg=24,inf=1e18,minf=-1e18;
      |                             ^~~~
sequence.cpp:38:39: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   38 | const int mxn=5e5,lg=24,inf=1e18,minf=-1e18;
      |                                       ^~~~~
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 0 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 2396 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 2548 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 0 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 2396 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 2548 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 179 ms 2512 KB Output is correct
14 Correct 176 ms 2516 KB Output is correct
15 Correct 128 ms 2516 KB Output is correct
16 Correct 129 ms 2520 KB Output is correct
17 Correct 94 ms 2644 KB Output is correct
18 Correct 217 ms 2516 KB Output is correct
19 Correct 178 ms 2392 KB Output is correct
20 Correct 149 ms 2644 KB Output is correct
21 Correct 176 ms 2512 KB Output is correct
22 Correct 184 ms 2520 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 46 ms 8560 KB Output is correct
3 Incorrect 49 ms 12100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

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

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 8536 KB Output is correct
2 Incorrect 45 ms 11716 KB Output isn't correct
3 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 0 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 2396 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 2548 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 179 ms 2512 KB Output is correct
14 Correct 176 ms 2516 KB Output is correct
15 Correct 128 ms 2516 KB Output is correct
16 Correct 129 ms 2520 KB Output is correct
17 Correct 94 ms 2644 KB Output is correct
18 Correct 217 ms 2516 KB Output is correct
19 Correct 178 ms 2392 KB Output is correct
20 Correct 149 ms 2644 KB Output is correct
21 Correct 176 ms 2512 KB Output is correct
22 Correct 184 ms 2520 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 0 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 2396 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 2548 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 179 ms 2512 KB Output is correct
14 Correct 176 ms 2516 KB Output is correct
15 Correct 128 ms 2516 KB Output is correct
16 Correct 129 ms 2520 KB Output is correct
17 Correct 94 ms 2644 KB Output is correct
18 Correct 217 ms 2516 KB Output is correct
19 Correct 178 ms 2392 KB Output is correct
20 Correct 149 ms 2644 KB Output is correct
21 Correct 176 ms 2512 KB Output is correct
22 Correct 184 ms 2520 KB Output is correct
23 Correct 46 ms 8560 KB Output is correct
24 Incorrect 49 ms 12100 KB Output isn't correct
25 Halted 0 ms 0 KB -