oj.uz

Submission #757420

# Submission time Handle Problem Language Result Execution time Memory
757420 2023-06-13T07:19:15 Z yellowtoad Sequence (APIO23_sequence) C++17
40 / 100
 2000 ms 56960 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 12020 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 6 ms 11996 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 12020 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 6 ms 11996 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 10 ms 12244 KB Output is correct
14 Correct 10 ms 12180 KB Output is correct
15 Correct 10 ms 12116 KB Output is correct
16 Correct 13 ms 12116 KB Output is correct
17 Correct 12 ms 12172 KB Output is correct
18 Correct 9 ms 12244 KB Output is correct
19 Correct 10 ms 12152 KB Output is correct
20 Correct 10 ms 12244 KB Output is correct
21 Correct 10 ms 12244 KB Output is correct
22 Correct 11 ms 12244 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Execution timed out 2062 ms 44684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 1118 ms 52992 KB Output is correct
3 Correct 1227 ms 52864 KB Output is correct
4 Correct 1219 ms 52860 KB Output is correct
5 Correct 1126 ms 53028 KB Output is correct
6 Correct 1164 ms 52944 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 56960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 12020 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 6 ms 11996 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 10 ms 12244 KB Output is correct
14 Correct 10 ms 12180 KB Output is correct
15 Correct 10 ms 12116 KB Output is correct
16 Correct 13 ms 12116 KB Output is correct
17 Correct 12 ms 12172 KB Output is correct
18 Correct 9 ms 12244 KB Output is correct
19 Correct 10 ms 12152 KB Output is correct
20 Correct 10 ms 12244 KB Output is correct
21 Correct 10 ms 12244 KB Output is correct
22 Correct 11 ms 12244 KB Output is correct
23 Incorrect 209 ms 22732 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 12020 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 6 ms 11996 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 10 ms 12244 KB Output is correct
14 Correct 10 ms 12180 KB Output is correct
15 Correct 10 ms 12116 KB Output is correct
16 Correct 13 ms 12116 KB Output is correct
17 Correct 12 ms 12172 KB Output is correct
18 Correct 9 ms 12244 KB Output is correct
19 Correct 10 ms 12152 KB Output is correct
20 Correct 10 ms 12244 KB Output is correct
21 Correct 10 ms 12244 KB Output is correct
22 Correct 11 ms 12244 KB Output is correct
23 Execution timed out 2062 ms 44684 KB Time limit exceeded
24 Halted 0 ms 0 KB -