Submission #990205

#	Time	Username	Problem	Language	Result	Execution time	Memory
990205		Mihailo	Sequence (APIO23_sequence)	C++17	0 / 100	146 ms	79912 KiB

sequence

#include "sequence.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
typedef long long ll;
using namespace std;

int n, g, tree[1000100], a[500100], m[500100], p1, p2;
vector<int> app[500100], v1, v2;

void update(int i, int x) {
    i+=g;
    tree[i]=x;
    i/=2;
    while(i>0) {
        tree[i]=tree[2*i]+tree[2*i+1];
        i/=2;
    }
}

int sum(int l, int r) {
    if(l>r) return 0;
    l+=g;
    r+=g;
    int rez=0;
    while(l<=r) {
        if(l%2) {
            rez+=tree[l];
            l++;
        }
        if(r%2==0) {
            rez+=tree[r];
            r--;
        }
        l/=2;
        r/=2;
    }
    return rez;
}

int solve() {
    g=1;
    while(g<n) g*=2;
    g--;
    for(int i=1; i<=n; i++) {
        app[a[i]].pb(i);
        m[i]=app[a[i]].size();
    }
    int rez=0;
    for(int i=1; i<=n; i++) update(i, 1);
    for(int i=1; i<=n; i++) {
        if(app[i].empty()) continue;
        for(int j=0; j<app[i].size(); j++) {
            update(app[i][j], 0);
        }
        if(sum(1, n)<0) return rez;
        for(int j=0; j<app[i].size(); j++) {
            update(app[i][j], -1);
        }
        for(int j=0; j<app[i].size(); j++) {
            if(v1.empty()||sum(1, v1.back()-1)<sum(1, app[i][j]-1)) v1.pb(app[i][j]);
        }
        for(int j=app[i].size()-1; j>=0; j--) {
            if(v2.empty()||sum(1, v2.back()-1)<sum(1, app[i][j]-1)) v2.pb(app[i][j]);
        }
        p1=0;
        p2=v2.size()-1;
        while(p2>=0) {
            if(sum(v1[p1], v2[p2])<=0) {
                rez=max(rez, m[v2[p2]]-m[v1[p1]]+1);
                p2--;
            }
            else p1++;
        }
        v1.clear();
        v2.clear();
    }
    return rez;
}

int sequence(int N, vector<int> A) {
    int rez=0;
    n=N;
    for(int i=0; i<N; i++) a[i+1]=A[i];
    rez=solve();
    for(int i=1; i<=n; i++) {
        app[i].clear();
    }
    for(int i=0; i<N; i++) a[i+1]=N+1-A[i];
    rez=max(rez, solve());
    for(int i=1; i<=n; i++) {
        app[i].clear();
    }
    return rez;
}

Compilation message (stderr)

sequence.cpp: In function 'int solve()':
sequence.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0; j<app[i].size(); j++) {
      |                      ~^~~~~~~~~~~~~~
sequence.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int j=0; j<app[i].size(); j++) {
      |                      ~^~~~~~~~~~~~~~
sequence.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j=0; j<app[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