oj.uz

Submission #757043

# Submission time Handle Problem Language Result Execution time Memory
757043 2023-06-12T12:53:17 Z doowey Sequence (APIO23_sequence) C++17
0 / 100
 2000 ms 45880 KB 
#include "sequence.h"
#include <bits/stdc++.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 + 10;
vector<int> pos[N];
int A[N];
int n;

struct Node{
    int low;
    int high;
    int lazy;
};

Node T[N * 4 + 512];

void build(int node, int cl, int cr){
    T[node].low = T[node].high = T[node].lazy = 0;
    if(cl == cr){
        T[node].low = T[node].high = cl;
        T[node].lazy = 0;
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node].low=min(T[node*2].low, T[node*2+1].low);
    T[node].high=max(T[node*2].high,T[node*2+1].high);
}

void push(int node, int cl, int cr){
    T[node].high += T[node].lazy;
    T[node].low += T[node].lazy;
    if(cl != cr){
        T[node * 2].lazy += T[node].lazy;
        T[node * 2 + 1].lazy += T[node].lazy;
    }
    T[node].lazy = 0;
}

void update_segm(int node, int cl, int cr, int tl, int tr, int d){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        T[node].lazy = d;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    update_segm(node * 2, cl, mid, tl, tr, d);
    update_segm(node * 2 + 1, mid + 1, cr, tl, tr, d);
    T[node].low=min(T[node*2].low, T[node*2+1].low);
    T[node].high=max(T[node*2].high,T[node*2+1].high);
}


pii get_val(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 mp(T[node].low, T[node].high);
    }
    int mid = (cl + cr) / 2;
    pii L = get_val(node * 2, cl, mid, tl, tr);
    pii R = get_val(node * 2 + 1, mid + 1, cr, tl, tr);
    return mp(min(L.fi, R.fi), max(L.se, R.se));
}

bool check(int cnt){
    build(1, 0, n);
    int bal;
    int l, r;
    pii suf;
    pii lE;
    pii rE;
    pii lef;
    int take;
    for(int cand = 1; cand <= n; cand ++ ){
        for(auto x : pos[cand]){
            update_segm(1, 0, n, x, n, -1);
        }
        for(int j = 0 ; j + cnt - 1 < pos[cand].size(); j ++ ){
            l = pos[cand][j];
            r = pos[cand][j + cnt - 1];
            lE = get_val(1, 0, n, l - 1, l - 1);
            rE = get_val(1, 0, n, r, r);
            bal = rE.fi - lE.fi;
            suf = get_val(1, 0, n, r, n);
            lef = get_val(1, 0, n, 0, l - 1);
            suf.fi -= rE.fi;
            suf.se -= rE.se;
            lef = mp(-lef.se, -lef.fi);
            lef.fi += lE.fi;
            lef.se += lE.fi;
            bal += lef.fi + suf.fi;
            take = max(0, (-cnt) - bal);
            if(bal <= cnt && take <= (lef.se - lef.fi) + (suf.se - suf.fi)){
                return true;
            }
        }
        for(auto x : pos[cand]){
            update_segm(1, 0, n, x, n, -1);
        }
    }
    return false;
}

int sequence(int _n, vector<int> a) {
    n = _n;
    for(int i = 0 ; i < n; i ++ ){
        A[i + 1] = a[i];
        pos[A[i + 1]].push_back(i + 1);
    }
    int l = 1;
    for(int ln = 19; ln >= 0 ;ln ++ ){
        if(l + (1 << ln) <= n && check(l + (1 << ln))){
            l += (1 << ln);
        }
    }
    return l;
}

Compilation message

sequence.cpp: In function 'bool check(int)':
sequence.cpp:91:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int j = 0 ; j + cnt - 1 < pos[cand].size(); j ++ ){
      |                         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:124:5: warning: iteration 2147483628 invokes undefined behavior [-Waggressive-loop-optimizations]
  124 |     for(int ln = 19; ln >= 0 ;ln ++ ){
      |     ^~~
sequence.cpp:124:25: note: within this loop
  124 |     for(int ln = 19; ln >= 0 ;ln ++ ){
      |                      ~~~^~~~

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 17.0

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

Subtask #3
0.0 / 7.0

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

Subtask #4
0.0 / 12.0

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

Subtask #5
0.0 / 13.0

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

Subtask #6
0.0 / 22.0

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

Subtask #7
0.0 / 18.0

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