oj.uz

Submission #757460

# Submission time Handle Problem Language Result Execution time Memory
757460 2023-06-13T08:14:54 Z yellowtoad Sequence (APIO23_sequence) C++17
40 / 100
 2000 ms 56952 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];
 
inline 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]);
}
 
inline 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]);
}
 
inline 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 9 ms 11948 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 12064 KB Output is correct
4 Correct 8 ms 12052 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 8 ms 11972 KB Output is correct
7 Correct 9 ms 11988 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Correct 7 ms 11972 KB Output is correct
10 Correct 7 ms 12020 KB Output is correct
11 Correct 7 ms 11988 KB Output is correct
12 Correct 9 ms 12024 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11948 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 12064 KB Output is correct
4 Correct 8 ms 12052 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 8 ms 11972 KB Output is correct
7 Correct 9 ms 11988 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Correct 7 ms 11972 KB Output is correct
10 Correct 7 ms 12020 KB Output is correct
11 Correct 7 ms 11988 KB Output is correct
12 Correct 9 ms 12024 KB Output is correct
13 Correct 12 ms 12260 KB Output is correct
14 Correct 10 ms 12244 KB Output is correct
15 Correct 10 ms 12116 KB Output is correct
16 Correct 10 ms 12232 KB Output is correct
17 Correct 12 ms 12188 KB Output is correct
18 Correct 9 ms 12244 KB Output is correct
19 Correct 10 ms 12148 KB Output is correct
20 Correct 11 ms 12252 KB Output is correct
21 Correct 10 ms 12244 KB Output is correct
22 Correct 14 ms 12252 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11948 KB Output is correct
2 Execution timed out 2077 ms 44544 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 1276 ms 53000 KB Output is correct
3 Correct 1435 ms 52888 KB Output is correct
4 Correct 1443 ms 52864 KB Output is correct
5 Correct 1368 ms 52984 KB Output is correct
6 Correct 1388 ms 52936 KB Output is correct

Subtask #5
0.0 / 13.0

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

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11948 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 12064 KB Output is correct
4 Correct 8 ms 12052 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 8 ms 11972 KB Output is correct
7 Correct 9 ms 11988 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Correct 7 ms 11972 KB Output is correct
10 Correct 7 ms 12020 KB Output is correct
11 Correct 7 ms 11988 KB Output is correct
12 Correct 9 ms 12024 KB Output is correct
13 Correct 12 ms 12260 KB Output is correct
14 Correct 10 ms 12244 KB Output is correct
15 Correct 10 ms 12116 KB Output is correct
16 Correct 10 ms 12232 KB Output is correct
17 Correct 12 ms 12188 KB Output is correct
18 Correct 9 ms 12244 KB Output is correct
19 Correct 10 ms 12148 KB Output is correct
20 Correct 11 ms 12252 KB Output is correct
21 Correct 10 ms 12244 KB Output is correct
22 Correct 14 ms 12252 KB Output is correct
23 Incorrect 232 ms 22796 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 9 ms 11948 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 12064 KB Output is correct
4 Correct 8 ms 12052 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 8 ms 11972 KB Output is correct
7 Correct 9 ms 11988 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Correct 7 ms 11972 KB Output is correct
10 Correct 7 ms 12020 KB Output is correct
11 Correct 7 ms 11988 KB Output is correct
12 Correct 9 ms 12024 KB Output is correct
13 Correct 12 ms 12260 KB Output is correct
14 Correct 10 ms 12244 KB Output is correct
15 Correct 10 ms 12116 KB Output is correct
16 Correct 10 ms 12232 KB Output is correct
17 Correct 12 ms 12188 KB Output is correct
18 Correct 9 ms 12244 KB Output is correct
19 Correct 10 ms 12148 KB Output is correct
20 Correct 11 ms 12252 KB Output is correct
21 Correct 10 ms 12244 KB Output is correct
22 Correct 14 ms 12252 KB Output is correct
23 Execution timed out 2077 ms 44544 KB Time limit exceeded
24 Halted 0 ms 0 KB -