Submission #757420

#	Time	Username	Problem	Language	Result	Execution time	Memory
757420		yellowtoad	Sequence (APIO23_sequence)	C++17	40 / 100	2073 ms	56960 KiB

sequence

#include "sequence.h"
#include <iostream>
#include <vector>
using namespace std;

int n, a[500010], maxx, node[2000010][2][2], lz[2000010][2][2]; // 0: updated, 1: not updated; 0: max, 1: min
vector<int> pos[500010];

void build(int id, int x, int y) {
    if (x == y) {
        node[id][0][0] = node[id][0][1] = node[id][1][1] = node[id][1][0] = x;
        return;
    }
    int mid = (x+y)/2;
    build(id*2,x,mid);
    build(id*2+1,mid+1,y);
    node[id][0][0] = max(node[id*2][0][0],node[id*2+1][0][0]);
    node[id][1][0] = max(node[id*2][1][0],node[id*2+1][1][0]);
    node[id][0][1] = min(node[id*2][0][1],node[id*2+1][0][1]);
    node[id][1][1] = min(node[id*2][1][1],node[id*2+1][1][1]);
}

void update(int i, int j, int id, int x, int y, int l, int r) {
    if ((l <= x) && (y <= r)) {
        node[id][i][j] -= 2;
        lz[id][i][j] -= 2;
        return;
    }
    if ((y < l) || (r < x)) return;
    int mid = (x+y)/2;
    node[id*2][i][j] += lz[id][i][j];
    node[id*2+1][i][j] += lz[id][i][j];
    lz[id*2][i][j] += lz[id][i][j];
    lz[id*2+1][i][j] += lz[id][i][j];
    lz[id][i][j] = 0;
    update(i,j,id*2,x,mid,l,r);
    update(i,j,id*2+1,mid+1,y,l,r);
    if (!j) node[id][i][j] = max(node[id*2][i][j],node[id*2+1][i][j]);
    else node[id][i][j] = min(node[id*2][i][j],node[id*2+1][i][j]);
}

int query(int i, int j, int id, int x, int y, int l, int r) {
    if ((l <= x) && (y <= r)) return node[id][i][j];
    if ((y < l) || (r < x)) {
        if (!j) return -1e9;
        else return 1e9;
    }
    int mid = (x+y)/2;
    node[id*2][i][j] += lz[id][i][j];
    node[id*2+1][i][j] += lz[id][i][j];
    lz[id*2][i][j] += lz[id][i][j];
    lz[id*2+1][i][j] += lz[id][i][j];
    lz[id][i][j] = 0;
    if (!j) return max(query(i,j,id*2,x,mid,l,r),query(i,j,id*2+1,mid+1,y,l,r));
    else return min(query(i,j,id*2,x,mid,l,r),query(i,j,id*2+1,mid+1,y,l,r));
}

int sequence(int N, std::vector<int> A) {
    n = N;
    for (int i = 1; i <= n; i++) {
        a[i] = A[i-1];
        pos[a[i]].push_back(i);
    }
    build(1,0,n);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < pos[i].size(); j++) {
            update(0,0,1,0,n,pos[i][j],n);
            update(0,1,1,0,n,pos[i][j],n);
        }
        int l = 0, r = 0;
        while (r < pos[i].size()) {
            if ((query(1,0,1,0,n,pos[i][r],n)-query(1,1,1,0,n,0,pos[i][l]-1))*(query(0,1,1,0,n,pos[i][r],n)-query(0,0,1,0,n,0,pos[i][l]-1)) <= 0) r++;
            else l++;
            maxx = max(maxx,r-l);
        }
        for (int j = 0; j < pos[i].size(); j++) {
            update(1,0,1,0,n,pos[i][j],n);
            update(1,1,1,0,n,pos[i][j],n);
        }
    }
    return maxx;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j = 0; j < pos[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
sequence.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while (r < pos[i].size()) {
      |                ~~^~~~~~~~~~~~~~~
sequence.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int j = 0; j < pos[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

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