Submission #1155322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155322		dnnnda	Cat Exercise (JOI23_ho_t4)	C++20	41 / 100	167 ms	16708 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
const int X=1000000007;

int p[200005], n, L[200005], R[200005];
ll seg[2][800005], ans;
#define m (l+r>>1)
#define L (id<<1)
#define R (id<<1|1)
void modify(int t, int pos, ll val, int l=0, int r=n, int id=1){
    //cout << "modify" << val << '\n';
    if(pos==l&&r==l+1){
        seg[t][id]=max(seg[t][id],val);
        return;
    }
    if(pos>=r||pos<l) return;
    modify(t,pos,val,l,m,L), modify(t,pos,val,m,r,R);
    seg[t][id]=max(seg[t][L],seg[t][R]);
}
ll query(int t, int ql, int qr, int l=0, int r=n, int id=1){
    //cout << "que" << ql << ' ' << qr << '\n';
    if(qr>=r&&ql<=l) return seg[t][id];
    if(qr<=l||ql>=r) return 0;
    return max(query(t,ql,qr,l,m,L),query(t,ql,qr,m,r,R));
}
#undef m
#undef L
#undef R

void init(){
    stack<int> stk;
    stk.push(-1);
    for(int i=0 ; i<n ; i++){
        while(stk.top()!=-1&&p[stk.top()]<p[i]) stk.pop();
        L[i]=stk.top();
        stk.push(i);
    }
    stack<int> stk2;
    stk2.push(n);
    for(int i=n-1 ; i>=0 ; i--){
        while(stk2.top()!=n&&p[stk2.top()]<p[i]) stk2.pop();
        R[i]=stk2.top();
        stk2.push(i);
    }
    /*
    for(int i=0 ; i<n ; i++) cout << L[i] << ' ';
    cout << '\n';
    for(int i=0 ; i<n ; i++) cout << R[i] << ' ';
    cout << '\n';
    */
    return;
}


signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(seg,0,sizeof seg);
    cin >> n;
    for(int i=0 ; i<n ; i++) cin >> p[i];
    init();
    for(int i=1 ; i<n ; i++){
        int a, b; cin >> a >> b;
    }
    vector<int> v;
    for(int i=0 ; i<n ; i++) v.push_back(i);
    sort(v.begin(),v.end(),[&](int a, int b){
         return p[a]<p[b];
    });
    for(int i:v){
        ll temp=max(query(0,i+1,R[i])-i,query(1,L[i]+1,i)-(n-i));
        temp=max(0LL,temp);
        ans=max(ans,temp);
        modify(0,i,temp+i);
        modify(1,i,temp+(n-i));
        //cout << i << ' ' << temp << '\n';
    }
    cout << ans << '\n';

    return 0;
}

void test(){
    string ss; cin >> ss;
    int n=ss.size();
    ss='.'+ss;
    while(1){
        int t; cin >> t;
        string s=ss;
        s[t]='R';
        while(t>=1&&t<=n){
            for(int i=1 ; i<=n ; i++){
                if(i==t) cout << '(';
                cout << s[i];
                if(i==t) cout << ')';
            }
            cout << '\n';
            if(s[t]=='R') s[t]='B', t++;
            else s[t]='R', t--;
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26