oj.uz

Submission #757589

# Submission time Handle Problem Language Result Execution time Memory
757589 2023-06-13T11:57:39 Z doowey Sequence (APIO23_sequence) C++17
7 / 100
 583 ms 64884 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 -- ){
            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;
            }
            update(1, 0, n, P[id][j], n, -2, 0);
        }
        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:96:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             while(j + soln < P[id].size()){
      |                   ~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 43348 KB Output is correct
2 Incorrect 20 ms 43348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 43348 KB Output is correct
2 Incorrect 20 ms 43348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 43348 KB Output is correct
2 Correct 465 ms 59160 KB Output is correct
3 Correct 456 ms 59152 KB Output is correct
4 Correct 497 ms 51224 KB Output is correct
5 Correct 421 ms 58216 KB Output is correct
6 Correct 414 ms 58120 KB Output is correct
7 Correct 380 ms 51704 KB Output is correct
8 Correct 428 ms 51848 KB Output is correct
9 Correct 474 ms 51808 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 43348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 64884 KB Output is correct
2 Correct 531 ms 64868 KB Output is correct
3 Correct 583 ms 64308 KB Output is correct
4 Correct 532 ms 64304 KB Output is correct
5 Incorrect 540 ms 60968 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 43348 KB Output is correct
2 Incorrect 20 ms 43348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 43348 KB Output is correct
2 Incorrect 20 ms 43348 KB Output isn't correct
3 Halted 0 ms 0 KB -