oj.uz

Submission #757592

# Submission time Handle Problem Language Result Execution time Memory
757592 2023-06-13T12:00:12 Z doowey Sequence (APIO23_sequence) C++17
69 / 100
 744 ms 64972 KB 
#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 + 100;
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

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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 43348 KB Output is correct
2 Correct 21 ms 43348 KB Output is correct
3 Correct 23 ms 43316 KB Output is correct
4 Correct 20 ms 43384 KB Output is correct
5 Correct 19 ms 43308 KB Output is correct
6 Correct 19 ms 43348 KB Output is correct
7 Correct 19 ms 43348 KB Output is correct
8 Correct 22 ms 43308 KB Output is correct
9 Correct 21 ms 43348 KB Output is correct
10 Correct 19 ms 43320 KB Output is correct
11 Correct 19 ms 43264 KB Output is correct
12 Correct 20 ms 43376 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 43348 KB Output is correct
2 Correct 21 ms 43348 KB Output is correct
3 Correct 23 ms 43316 KB Output is correct
4 Correct 20 ms 43384 KB Output is correct
5 Correct 19 ms 43308 KB Output is correct
6 Correct 19 ms 43348 KB Output is correct
7 Correct 19 ms 43348 KB Output is correct
8 Correct 22 ms 43308 KB Output is correct
9 Correct 21 ms 43348 KB Output is correct
10 Correct 19 ms 43320 KB Output is correct
11 Correct 19 ms 43264 KB Output is correct
12 Correct 20 ms 43376 KB Output is correct
13 Correct 20 ms 43332 KB Output is correct
14 Correct 20 ms 43412 KB Output is correct
15 Correct 24 ms 43420 KB Output is correct
16 Correct 22 ms 43340 KB Output is correct
17 Correct 21 ms 43348 KB Output is correct
18 Correct 21 ms 43348 KB Output is correct
19 Correct 21 ms 43432 KB Output is correct
20 Correct 20 ms 43340 KB Output is correct
21 Correct 22 ms 43348 KB Output is correct
22 Correct 21 ms 43348 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 43348 KB Output is correct
2 Correct 439 ms 59144 KB Output is correct
3 Correct 414 ms 59160 KB Output is correct
4 Correct 508 ms 51336 KB Output is correct
5 Correct 413 ms 58212 KB Output is correct
6 Correct 417 ms 58216 KB Output is correct
7 Correct 422 ms 51860 KB Output is correct
8 Correct 440 ms 51856 KB Output is correct
9 Correct 487 ms 51808 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 43348 KB Output is correct
2 Correct 567 ms 52164 KB Output is correct
3 Correct 611 ms 51344 KB Output is correct
4 Correct 553 ms 51256 KB Output is correct
5 Correct 744 ms 52220 KB Output is correct
6 Correct 626 ms 51512 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 64888 KB Output is correct
2 Correct 576 ms 64972 KB Output is correct
3 Correct 532 ms 64312 KB Output is correct
4 Correct 553 ms 64332 KB Output is correct
5 Correct 542 ms 60880 KB Output is correct
6 Correct 514 ms 60948 KB Output is correct
7 Correct 495 ms 59784 KB Output is correct
8 Incorrect 500 ms 59340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 43348 KB Output is correct
2 Correct 21 ms 43348 KB Output is correct
3 Correct 23 ms 43316 KB Output is correct
4 Correct 20 ms 43384 KB Output is correct
5 Correct 19 ms 43308 KB Output is correct
6 Correct 19 ms 43348 KB Output is correct
7 Correct 19 ms 43348 KB Output is correct
8 Correct 22 ms 43308 KB Output is correct
9 Correct 21 ms 43348 KB Output is correct
10 Correct 19 ms 43320 KB Output is correct
11 Correct 19 ms 43264 KB Output is correct
12 Correct 20 ms 43376 KB Output is correct
13 Correct 20 ms 43332 KB Output is correct
14 Correct 20 ms 43412 KB Output is correct
15 Correct 24 ms 43420 KB Output is correct
16 Correct 22 ms 43340 KB Output is correct
17 Correct 21 ms 43348 KB Output is correct
18 Correct 21 ms 43348 KB Output is correct
19 Correct 21 ms 43432 KB Output is correct
20 Correct 20 ms 43340 KB Output is correct
21 Correct 22 ms 43348 KB Output is correct
22 Correct 21 ms 43348 KB Output is correct
23 Correct 96 ms 45892 KB Output is correct
24 Correct 94 ms 45780 KB Output is correct
25 Correct 100 ms 45896 KB Output is correct
26 Correct 98 ms 44884 KB Output is correct
27 Correct 104 ms 44984 KB Output is correct
28 Correct 121 ms 44980 KB Output is correct
29 Correct 95 ms 44628 KB Output is correct
30 Correct 98 ms 44772 KB Output is correct
31 Correct 110 ms 44832 KB Output is correct
32 Correct 77 ms 46896 KB Output is correct
33 Correct 99 ms 45708 KB Output is correct
34 Correct 91 ms 45672 KB Output is correct
35 Correct 99 ms 45620 KB Output is correct
36 Correct 105 ms 45608 KB Output is correct
37 Correct 117 ms 45772 KB Output is correct
38 Correct 99 ms 45644 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 43348 KB Output is correct
2 Correct 21 ms 43348 KB Output is correct
3 Correct 23 ms 43316 KB Output is correct
4 Correct 20 ms 43384 KB Output is correct
5 Correct 19 ms 43308 KB Output is correct
6 Correct 19 ms 43348 KB Output is correct
7 Correct 19 ms 43348 KB Output is correct
8 Correct 22 ms 43308 KB Output is correct
9 Correct 21 ms 43348 KB Output is correct
10 Correct 19 ms 43320 KB Output is correct
11 Correct 19 ms 43264 KB Output is correct
12 Correct 20 ms 43376 KB Output is correct
13 Correct 20 ms 43332 KB Output is correct
14 Correct 20 ms 43412 KB Output is correct
15 Correct 24 ms 43420 KB Output is correct
16 Correct 22 ms 43340 KB Output is correct
17 Correct 21 ms 43348 KB Output is correct
18 Correct 21 ms 43348 KB Output is correct
19 Correct 21 ms 43432 KB Output is correct
20 Correct 20 ms 43340 KB Output is correct
21 Correct 22 ms 43348 KB Output is correct
22 Correct 21 ms 43348 KB Output is correct
23 Correct 439 ms 59144 KB Output is correct
24 Correct 414 ms 59160 KB Output is correct
25 Correct 508 ms 51336 KB Output is correct
26 Correct 413 ms 58212 KB Output is correct
27 Correct 417 ms 58216 KB Output is correct
28 Correct 422 ms 51860 KB Output is correct
29 Correct 440 ms 51856 KB Output is correct
30 Correct 487 ms 51808 KB Output is correct
31 Correct 567 ms 52164 KB Output is correct
32 Correct 611 ms 51344 KB Output is correct
33 Correct 553 ms 51256 KB Output is correct
34 Correct 744 ms 52220 KB Output is correct
35 Correct 626 ms 51512 KB Output is correct
36 Correct 610 ms 64888 KB Output is correct
37 Correct 576 ms 64972 KB Output is correct
38 Correct 532 ms 64312 KB Output is correct
39 Correct 553 ms 64332 KB Output is correct
40 Correct 542 ms 60880 KB Output is correct
41 Correct 514 ms 60948 KB Output is correct
42 Correct 495 ms 59784 KB Output is correct
43 Incorrect 500 ms 59340 KB Output isn't correct
44 Halted 0 ms 0 KB -