oj.uz

Submission #750017

# Submission time Handle Problem Language Result Execution time Memory
750017 2023-05-29T04:22:03 Z Cookie Sequence (APIO23_sequence) C++17
0 / 100
 760 ms 64628 KB 
#include<bits/stdc++.h>
#include "sequence.h"
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 5e5;
const ll prec = 1e-6;
struct ST{
    // range min prefix, range update
    int st[4 * mxn + 1], lz[4 * mxn + 1];
    void push(int nd, int l, int mid, int r){
        lz[nd << 1] += lz[nd]; lz[nd << 1 | 1] += lz[nd];
        st[nd << 1] += lz[nd]; st[nd << 1 | 1] += lz[nd];
        lz[nd] = 0;
    }
    void init(int nd, int l, int r){
        if(l == r){
            st[nd] = -l;
            return;
        }
        int mid = (l + r) >> 1;
        init(nd << 1, l, mid); init(nd << 1 | 1, mid + 1, r);
        st[nd] = min(st[nd << 1], st[nd << 1 | 1]);
    }
    void upd(int nd, int l, int r, int ql, int qr, int v){
        if(ql > r || qr < l)return;
        if(ql <= l && qr >= r){
            st[nd] += v; lz[nd] += v;
            return;
        }
        int mid = (l + r) >> 1;
        push(nd, l, mid, r);
        upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v);
        st[nd] = min(st[nd << 1], st[nd << 1 | 1]);
    }
    int get(int nd, int l, int r, int ql, int qr){
        if(ql > r || qr < l)return(1e9);
        if(ql <= l && qr >= r)return(st[nd]);
        int mid = (l + r) >> 1;
        push(nd, l, mid, r);
        return(min(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
    }
};
struct ST2{
    // range max prefix, range update
    int st[4 * mxn + 1], lz[4 * mxn + 1];
    void push(int nd, int l, int mid, int r){
        lz[nd << 1] += lz[nd]; lz[nd << 1 | 1] += lz[nd];
        st[nd << 1] += lz[nd]; st[nd << 1 | 1] += lz[nd];
        lz[nd] = 0;
        return;
    }
    void init(int nd, int l, int r){
        if(l == r){
            st[nd] = -l;
            return;
        }
        int mid = (l + r) >> 1;
        init(nd << 1, l, mid); init(nd << 1 | 1, mid + 1, r);
        st[nd] = max(st[nd << 1], st[nd << 1 | 1]);
    }
    void upd(int nd, int l, int r, int ql, int qr, int v){
        if(ql > r || qr < l)return;
        if(ql <= l && qr >= r){
            st[nd] += v; lz[nd] += v;
            return;
        }
        int mid = (l + r) >> 1;
        push(nd, l, mid, r);
        upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v);
        st[nd] = max(st[nd << 1], st[nd << 1 | 1]);
    }
    int get(int nd, int l, int r, int ql, int qr){
        if(ql > r || qr < l)return(-1e9);
        if(ql <= l && qr >= r)return(st[nd]);
        int mid = (l + r) >> 1;
        push(nd, l, mid, r);
        return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
    }
};
ST large, equa;
ST2 large2, equa2;
vt<int>comp[mxn + 1];
int sequence(int n, std::vector<int> a) {
   large.init(1, 0, n); equa.init(1, 0, n); large2.init(1, 0, n); equa2.init(1, 0, n);
   for(int i = 0; i < n; i++){
       comp[a[i]].pb(i + 1);
   }
   int ans = 1;
   
   for(int i = 1; i <= n; i++){
       for(auto j: comp[i]){
           equa.upd(1, 0, n, j, n, 2); equa2.upd(1, 0, n, j, n,2);
       }
       
       int r = 1;
       for(int j = 0; j < sz(comp[i]) - 1; j++){
           r = max(r, j + 1);
           
           while(r < sz(comp[i])){
               ll lar = large2.get(1, 0, n, comp[i][r], n) - large.get(1, 0, n, 0, comp[i][j] - 1);
               ll equ = equa2.get(1, 0, n, comp[i][r], n) - equa.get(1, 0, n, 0, comp[i][j] - 1);
               //if(i == 1 && j = 0)
               if(equ >= 0 && lar <= 0){
                   r++;
               }else{
                   break;
               }
           }
           
           ans = max(ans, r - j);
       }
       
       for(auto j: comp[i]){
           large.upd(1, 0, n, j, n,2); large2.upd(1, 0, n, j, n,2);
       }
   }
   
  return ans;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12116 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Incorrect 7 ms 12128 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12116 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Incorrect 7 ms 12128 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12116 KB Output is correct
2 Incorrect 609 ms 58772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 672 ms 51144 KB Output is correct
3 Correct 728 ms 50980 KB Output is correct
4 Incorrect 760 ms 51028 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 64572 KB Output is correct
2 Correct 710 ms 64628 KB Output is correct
3 Incorrect 654 ms 64108 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12116 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Incorrect 7 ms 12128 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12116 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Incorrect 7 ms 12128 KB Output isn't correct
5 Halted 0 ms 0 KB -