Submission #750019

#	Time	Username	Problem	Language	Result	Execution time	Memory
750019		Cookie	Sequence (APIO23_sequence)	C++17	100 / 100	1139 ms	64636 KiB

sequence

#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 = large.get(1, 0, n, comp[i][r], n) - large2.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: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 18 / 18