oj.uz

Submission #757590

# Submission time Handle Problem Language Result Execution time Memory
757590 2023-06-13T11:58:12 Z doowey Sequence (APIO23_sequence) C++17
69 / 100
 661 ms 64900 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 + 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

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 19 ms 43320 KB Output is correct
2 Correct 20 ms 43348 KB Output is correct
3 Correct 19 ms 43324 KB Output is correct
4 Correct 22 ms 43372 KB Output is correct
5 Correct 20 ms 43368 KB Output is correct
6 Correct 24 ms 43328 KB Output is correct
7 Correct 25 ms 43340 KB Output is correct
8 Correct 27 ms 43252 KB Output is correct
9 Correct 20 ms 43348 KB Output is correct
10 Correct 20 ms 43248 KB Output is correct
11 Correct 19 ms 43264 KB Output is correct
12 Correct 19 ms 43272 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 43320 KB Output is correct
2 Correct 20 ms 43348 KB Output is correct
3 Correct 19 ms 43324 KB Output is correct
4 Correct 22 ms 43372 KB Output is correct
5 Correct 20 ms 43368 KB Output is correct
6 Correct 24 ms 43328 KB Output is correct
7 Correct 25 ms 43340 KB Output is correct
8 Correct 27 ms 43252 KB Output is correct
9 Correct 20 ms 43348 KB Output is correct
10 Correct 20 ms 43248 KB Output is correct
11 Correct 19 ms 43264 KB Output is correct
12 Correct 19 ms 43272 KB Output is correct
13 Correct 20 ms 43352 KB Output is correct
14 Correct 25 ms 43348 KB Output is correct
15 Correct 21 ms 43408 KB Output is correct
16 Correct 21 ms 43348 KB Output is correct
17 Correct 23 ms 43356 KB Output is correct
18 Correct 21 ms 43372 KB Output is correct
19 Correct 21 ms 43360 KB Output is correct
20 Correct 23 ms 43392 KB Output is correct
21 Correct 21 ms 43404 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 19 ms 43320 KB Output is correct
2 Correct 425 ms 59232 KB Output is correct
3 Correct 426 ms 59152 KB Output is correct
4 Correct 486 ms 51412 KB Output is correct
5 Correct 417 ms 58208 KB Output is correct
6 Correct 422 ms 58208 KB Output is correct
7 Correct 421 ms 51696 KB Output is correct
8 Correct 438 ms 51712 KB Output is correct
9 Correct 496 ms 51744 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 43348 KB Output is correct
2 Correct 584 ms 52220 KB Output is correct
3 Correct 595 ms 51328 KB Output is correct
4 Correct 586 ms 51328 KB Output is correct
5 Correct 661 ms 52244 KB Output is correct
6 Correct 630 ms 51516 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 64900 KB Output is correct
2 Correct 537 ms 64872 KB Output is correct
3 Correct 556 ms 64400 KB Output is correct
4 Correct 534 ms 64304 KB Output is correct
5 Correct 549 ms 60888 KB Output is correct
6 Correct 526 ms 61064 KB Output is correct
7 Correct 535 ms 59768 KB Output is correct
8 Incorrect 485 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 19 ms 43320 KB Output is correct
2 Correct 20 ms 43348 KB Output is correct
3 Correct 19 ms 43324 KB Output is correct
4 Correct 22 ms 43372 KB Output is correct
5 Correct 20 ms 43368 KB Output is correct
6 Correct 24 ms 43328 KB Output is correct
7 Correct 25 ms 43340 KB Output is correct
8 Correct 27 ms 43252 KB Output is correct
9 Correct 20 ms 43348 KB Output is correct
10 Correct 20 ms 43248 KB Output is correct
11 Correct 19 ms 43264 KB Output is correct
12 Correct 19 ms 43272 KB Output is correct
13 Correct 20 ms 43352 KB Output is correct
14 Correct 25 ms 43348 KB Output is correct
15 Correct 21 ms 43408 KB Output is correct
16 Correct 21 ms 43348 KB Output is correct
17 Correct 23 ms 43356 KB Output is correct
18 Correct 21 ms 43372 KB Output is correct
19 Correct 21 ms 43360 KB Output is correct
20 Correct 23 ms 43392 KB Output is correct
21 Correct 21 ms 43404 KB Output is correct
22 Correct 21 ms 43348 KB Output is correct
23 Correct 99 ms 45892 KB Output is correct
24 Correct 105 ms 45892 KB Output is correct
25 Correct 109 ms 45852 KB Output is correct
26 Correct 107 ms 44884 KB Output is correct
27 Correct 103 ms 44972 KB Output is correct
28 Correct 138 ms 44968 KB Output is correct
29 Correct 99 ms 44700 KB Output is correct
30 Correct 90 ms 44768 KB Output is correct
31 Correct 104 ms 44848 KB Output is correct
32 Correct 83 ms 46808 KB Output is correct
33 Correct 118 ms 45708 KB Output is correct
34 Correct 100 ms 45652 KB Output is correct
35 Correct 107 ms 45620 KB Output is correct
36 Correct 89 ms 45628 KB Output is correct
37 Correct 93 ms 45688 KB Output is correct
38 Correct 97 ms 45620 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 43320 KB Output is correct
2 Correct 20 ms 43348 KB Output is correct
3 Correct 19 ms 43324 KB Output is correct
4 Correct 22 ms 43372 KB Output is correct
5 Correct 20 ms 43368 KB Output is correct
6 Correct 24 ms 43328 KB Output is correct
7 Correct 25 ms 43340 KB Output is correct
8 Correct 27 ms 43252 KB Output is correct
9 Correct 20 ms 43348 KB Output is correct
10 Correct 20 ms 43248 KB Output is correct
11 Correct 19 ms 43264 KB Output is correct
12 Correct 19 ms 43272 KB Output is correct
13 Correct 20 ms 43352 KB Output is correct
14 Correct 25 ms 43348 KB Output is correct
15 Correct 21 ms 43408 KB Output is correct
16 Correct 21 ms 43348 KB Output is correct
17 Correct 23 ms 43356 KB Output is correct
18 Correct 21 ms 43372 KB Output is correct
19 Correct 21 ms 43360 KB Output is correct
20 Correct 23 ms 43392 KB Output is correct
21 Correct 21 ms 43404 KB Output is correct
22 Correct 21 ms 43348 KB Output is correct
23 Correct 425 ms 59232 KB Output is correct
24 Correct 426 ms 59152 KB Output is correct
25 Correct 486 ms 51412 KB Output is correct
26 Correct 417 ms 58208 KB Output is correct
27 Correct 422 ms 58208 KB Output is correct
28 Correct 421 ms 51696 KB Output is correct
29 Correct 438 ms 51712 KB Output is correct
30 Correct 496 ms 51744 KB Output is correct
31 Correct 584 ms 52220 KB Output is correct
32 Correct 595 ms 51328 KB Output is correct
33 Correct 586 ms 51328 KB Output is correct
34 Correct 661 ms 52244 KB Output is correct
35 Correct 630 ms 51516 KB Output is correct
36 Correct 560 ms 64900 KB Output is correct
37 Correct 537 ms 64872 KB Output is correct
38 Correct 556 ms 64400 KB Output is correct
39 Correct 534 ms 64304 KB Output is correct
40 Correct 549 ms 60888 KB Output is correct
41 Correct 526 ms 61064 KB Output is correct
42 Correct 535 ms 59768 KB Output is correct
43 Incorrect 485 ms 59340 KB Output isn't correct
44 Halted 0 ms 0 KB -