Submission #955048

#	Time	Username	Problem	Language	Result	Execution time	Memory
955048		Otalp	Sequence (APIO23_sequence)	C++17	28 / 100	2089 ms	14788 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second

int a[500100];
int s1[500100], s2[500100], c[500100];



int sequence(int n, vector<int> A) {
    int ans = 0;
    for(int i=1; i<=n; i++){
        a[i] = A[i - 1];
    }
    for(int x=1; x<=n; x++){
        vector<pii> q;
        int mn=0, mx=0, sum=0;
        for(int i=1; i<=n; i++){
            if(a[i] == x){
                q.pb({mn, mx});
                mn = 1e9;
                mx = -1e9;
            }
            if(a[i] > x){
                sum += 1;
            }
            if(a[i] < x){
                sum -= 1;
            }
            mn = min(mn, sum);
            mx = max(mx, sum);
        }
        q.pb({mn, mx});
        //cout<<x<<'\n';
        for(int i=0; i<q.size(); i++){
            //cout<<q[i].ff<<' '<<q[i].ss<<'\n';
            for(int j=0; j<i; j++){
                int x = q[i].ff - q[j].ss, y = q[i].ss - q[j].ff;
                if(abs(x) <= i - j or abs(y) <= i - j or (x == abs(x)) != (y == abs(y))){
                    ans = max(ans, i - j);
                }
            }
        }
    }
    return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=0; i<q.size(); i++){
      |                      ~^~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18