Submission #757590

#	Time	Username	Problem	Language	Result	Execution time	Memory
757590		doowey	Sequence (APIO23_sequence)	C++17	69 / 100	661 ms	64900 KiB

sequence

#include <bits/stdc++.h>
#include "sequence.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)5e5 + 5;
int n;
int A[N];
vector<int> P[N];

struct Node{
    pii can;
    int lazyL;
    int lazyR;
};

Node T[N * 4 + 500];

Node unite(Node ai, Node bi){
    Node res;
    res.can = mp(min(ai.can.fi, bi.can.fi), max(ai.can.se, bi.can.se));
    res.lazyL = res.lazyR = 0;
    return res;
}


void push(int node, int cl, int cr){
    T[node].can.fi += T[node].lazyL;
    T[node].can.se += T[node].lazyR;
    if(cl != cr){
        T[node * 2].lazyL += T[node].lazyL;
        T[node * 2].lazyR += T[node].lazyR;
        T[node * 2 + 1].lazyL += T[node].lazyL;
        T[node * 2 + 1].lazyR += T[node].lazyR;
    }
    T[node].lazyL = T[node].lazyR = 0;
}

void update(int node, int cl, int cr, int tl, int tr, int vl, int vr){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        T[node].lazyL = vl;
        T[node].lazyR = vr;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    update(node * 2, cl, mid, tl, tr, vl, vr);
    update(node * 2 + 1, mid + 1, cr, tl, tr, vl, vr);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}

pii get(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return mp((int)1e9, -(int)1e9);
    if(cl >= tl && cr <= tr){
        return T[node].can;
    }
    int mid = (cl + cr) / 2;
    pii lf = get(node * 2, cl, mid, tl, tr);
    pii rf = get(node * 2 + 1, mid + 1, cr, tl, tr);
    return mp(min(lf.fi, rf.fi), max(lf.se, rf.se));
}

void build(int node, int cl, int cr){
    T[node].can = mp(cl, cl);
    if(cl == cr){
        T[node].lazyL = T[node].lazyR = 0;
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
}

int sequence(int _n, vector<int> _a) {
    n = _n;
    for(int i = 1; i <= n; i ++ ){
        A[i] = _a[i - 1];
        P[A[i]].push_back(i);
    }
    int soln = 1;
    build(1, 0, n);
    int l, r;
    pii A, B;
    for(int id = 1; id <= n; id ++ ){
        for(int j = (int)P[id].size() - 1 ; j >= 0; j -- ){
            update(1, 0, n, P[id][j], n, -2, 0);
            while(j + soln < P[id].size()){
                l = P[id][j];
                r = P[id][j + soln];
                A = get(1, 0, n, 0, l - 1);
                B = get(1, 0, n, r, n);
                if(max(A.fi,B.fi) <= min(A.se,B.se)) {
                    soln ++ ;
                }
                else break;
            }
        }
        for(auto x : P[id]){
            update(1, 0, n, x, n, 0, -2);
        }
    }
    return soln;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:97:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             while(j + soln < P[id].size()){
      |                   ~~~~~~~~~^~~~~~~~~~~~~~

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