제출 #1243775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243775		JelaByteEngineer	Global Warming (CEOI18_glo)	C++20	100 / 100	413 ms	22328 KiB

glo

#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> st;
vector <vector <int>> mat;
void upd (int idx, int node, int l, int r, int ind, int x)
{
    if (l==r)
    {
        mat[idx][l]+=x; st[idx][node]+=x;
        return;
    }
    int mid=(l+r)/2;
    if (ind<=mid)
    {
        upd(idx, 2*node, l, mid, ind, x);
    }
    else upd(idx, 2*node+1, mid+1, r, ind, x);
    st[idx][node]=max(st[idx][2*node], st[idx][2*node+1]);
}
int query (int idx, int node, int l, int r, int askl, int askr)
{
    if (askl>r || askr<l) return 0;
    if (askl<=l && askr>=r) return st[idx][node];
    int mid=(l+r)/2;
    return max(query(idx, 2*node, l, mid, askl, askr), query(idx, 2*node+1, mid+1, r, askl, askr));
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x; cin>>n>>x;
    vector <int> niz(n);
    for (int i=0; i<n; i++) cin>>niz[i];
    vector <int> niz1(n);
    niz1=niz;
    reverse(niz.begin(), niz.end());
    sort (niz1.begin(), niz1.end());
    map <int, int> mapa;
    for (int i=n-1; i>=0; i--) mapa[niz1[i]]=i;
    mat.resize(2, vector <int> (n, 0));
    st.resize(2, vector <int> (4*n, 0));
    //nulti je bez, prvi je sa
    for (int i=0; i<n; i++)
    {
        //cout<<"i je: "<<i<<" znaci na redu je: "<<niz[i]<<endl;
        int ind=mapa[niz[i]];
        upd(0, 1, 0, n-1, ind, 1); upd(1, 1, 0, n-1, ind, 1);
        //cout<<"njegov ind je: "<<ind<<endl;
        int upd1=(ind<n-1? query(0, 1, 0, n-1, ind+1, n-1):0);
        //cout<<"upd1 je: "<<upd1<<endl;
        upd(0, 1, 0, n-1, ind, upd1);
        int lo=lower_bound(niz1.begin(), niz1.end(), niz[i]-x+1)-niz1.begin();
        int upd2=max((ind<n-1? query(1, 1, 0, n-1, ind+1, n-1):0), (ind>0? query(0, 1, 0, n-1, lo, ind-1):0));
        //cout<<"upd2 je: "<<upd2<<endl;
        upd(1, 1, 0, n-1, ind, upd2);
        /*cout<<"trenutno stanje matrice je: "<<endl;
        for (int j=0; j<n; j++) cout<<niz1[j]<<" ";
        cout<<endl;
        for (int j=0; j<2; j++)
        {
            for (int k=0; k<n; k++) cout<<mat[j][k]<<" ";
            cout<<endl;
        }*/
        mapa[niz[i]]++;
    }
    int ans=0;
    for (int i=0; i<n; i++)
    {
        ans=max({ans, mat[1][i], mat[0][i]});
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25