Submission #955006

#	Time	Username	Problem	Language	Result	Execution time	Memory
955006		Otalp	Sequence (APIO23_sequence)	C++17	11 / 100	2077 ms	171348 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];
struct node{
    int x=1e9;
    node *l = nullptr, *r = nullptr;
    node(){}
};

node *t = new node();


void upd(node *v, int l, int r, int pos, int x){
    if(l == r){
        v -> x = min(v -> x, x);
        return;
    }
    int mid = floor(((double)l + (double)r) / 2);
    if(mid >= pos){
        if(!v -> l) v->l = new node();
        upd(v -> l, l, mid, pos, x);
    }
    else{
        if(!v -> r) v->r = new node();
        upd(v->r, mid+1, r, pos, x);
    }
    v -> x = 1e9;
    if(v -> l) v -> x = min(v -> x, v -> l -> x);
    if(v -> r) v -> x = min(v -> x, v -> r -> x);
}

int get(node *v, int l, int r, int L, int R){
    if(r < L or R < l){
        return 1e9;
    }
    if(L <= l and r <= R){
        return v -> x;
    }
    int mid=floor(((double)l + (double)r) / 2);
    int x = 1e9;
    if(v -> l) x = min(x, get(v->l, l, mid, L, R));
    if(v -> r) x = min(x, get(v->r, mid+1, r, L, R));
    return x;
}







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<pair<int, pii> > q;
        for(int i=1; i<=n; i++){
            if(a[i] == x) s1[i] = s1[i - 1] + 1, s2[i] = s2[i - 1] + 1, c[i] = c[i - 1] + 1;
            if(a[i] > x) s1[i] = s1[i - 1] + 1, s2[i] = s2[i - 1] - 1, c[i] = c[i - 1];
            if(a[i] < x) s1[i] = s1[i - 1] - 1, s2[i] = s2[i - 1] + 1, c[i] = c[i - 1];
            q.pb({s1[i], {s2[i], i}});
        }
        t = new node();
        q.pb({0, {0, 0}});
        sort(q.begin(), q.end());
        for(int i=0; i<q.size(); i++){
            int x=q[i].ss.ff, pos=q[i].ss.ss;
            upd(t, -n, n, x, pos);
            int h = get(t, -n, n, -n, x);
            if(h <= pos){
                ans = max(ans, c[pos] - c[h]);
            }
        }


        
    }
    return ans;
}

Compilation message (stderr)

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

• Subtask 1: 11 / 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