Submission #823744

#	Time	Username	Problem	Language	Result	Execution time	Memory
823744		hmm789	Sequence (APIO23_sequence)	C++17	0 / 100	48 ms	15980 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;

int sequence(int N, std::vector<int> A) {
    #define int long long
    int ans = 0, tup = 1, tdown = 0;
    vector<pair<int, int>> up, down;
    bool f = true; // true -> up, false -> down
    up.push_back({A[0], 1});
    for(int i = 1; i < N; i++) {
        if(A[i] < A[i-1]) f = false;
        if(f) {
            if(A[i] == up.back().first) {
                up.back().second++;
            } else {
                up.push_back({A[i], 1});
            }
            tup++;
        } else {
            if(!down.empty() && A[i] == down.back().first) {
                down.back().second++;
            } else {
                down.push_back({A[i], 1});
            }
            tdown++;
        }
    }
    int i1 = 0, i2 = down.size()-1;
    while(i1 < up.size() && i2 >= 0) {
        if(up[i1].first < down[i2].first) {
            ans = max(ans, up[i1].second);
            tup -= up[i1].second;
            i1++;
        } else if(up[i1].first > down[i2].first) {
            ans = max(ans, down[i2].second);
            tdown -= down[i2].second;
            i2--;
        } else {
            if(tup+tdown-up[i1].second-down[i2].second <= N/2) ans = max(ans, up[i1].second+down[i2].second);
            tup -= up[i1].second;
            tdown -= down[i2].second;
            i1++;
            i2--;
        }
    }
    while(i1 < up.size()) {
        ans = max(ans, up[i1].second);
        i1++;
    }
    while(i2 >= 0) {
        ans = max(ans, down[i2].second);
        i2--;
    }
    return ans;
    #undef int
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:30:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     while(i1 < up.size() && i2 >= 0) {
      |           ~~~^~~~~~~~~~~
sequence.cpp:47:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     while(i1 < up.size()) {
      |           ~~~^~~~~~~~~~~

• 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