Submission #1190195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190195		Unforgettablepl	Measures (CEOI22_measures)	C++20	76 / 100	444 ms	50604 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct segtree{
    vector<int> tree,lazy;
    int N;
    segtree(int N):N(N),tree(4*N,-1e18),lazy(8*N){}
    void update(int L,int R,int x,int qL,int qR,int qX){
        if(lazy[x]){
            tree[x]+=lazy[x];
            lazy[2*x]+=lazy[x];
            lazy[2*x+1]+=lazy[x];
            lazy[x]=0;
        }
        if(qR<L or R<qL)return;
        if(qL<=L and R<=qR){
            tree[x]+=qX;
            lazy[2*x]+=qX;
            lazy[2*x+1]+=qX;
            return;
        }
        int mid = (L+R)/2;
        update(L,mid,2*x,qL,qR,qX);
        update(mid+1,R,2*x+1,qL,qR,qX);
        tree[x]=max(tree[2*x],tree[2*x+1]);
    }
    void update(int qL,int qR,int qX){
        update(1,N,1,qL,qR,qX);
    }
    int get(int L,int R,int x,int qL,int qR){
        if(lazy[x]){
            tree[x]+=lazy[x];
            lazy[2*x]+=lazy[x];
            lazy[2*x+1]+=lazy[x];
            lazy[x]=0;
        }
        if(qR<L or R<qL)return -2e18;
        if(qL<=L and R<=qR)return tree[x];
        int mid = (L+R)/2;
        return max(get(L,mid,2*x,qL,qR),get(mid+1,R,2*x+1,qL,qR));
    }
    int get(int qL,int qR){
        return get(1,N,1,qL,qR);
    }
};

struct fenwick{
    vector<int> tree;
    fenwick(int N):tree(N+1){}
    int get(int k){
        int ans = 0;
        while(k){
            ans+=tree[k];
            k-=k&-k;
        }
        return ans;
    }
    void add(int k,int x){
        while(k<tree.size()){
            tree[k]+=x;
            k+=k&-k;
        }
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M,D;
    cin >> N >> M >> D;
    vector<pair<int,int>> queries(M);
    vector<int> queriesa(M);
    for(int i=0;i<M;i++){
        cin >> queries[i].first;
        queriesa[i]=queries[i].first;
        queries[i].second = i+1;
    }
    sort(queries.begin(),queries.end());
    vector<int> newidx(M+1);
    vector<int> newidxPref(M+1);
    fenwick bit(M);
    for(int i=1;i<=M;i++){
        newidxPref[queries[i-1].second]=bit.get(queries[i-1].second);
        newidx[queries[i-1].second]=i;
        bit.add(queries[i-1].second,1);
    }
    segtree seggyMini(M);
    segtree seggyMaxi(M);
    int ans = 0;
    for(int i=1;i<=M;i++){
        seggyMaxi.update(newidx[i],M,+D);
        seggyMini.update(newidx[i],M,-D);
        seggyMaxi.update(newidx[i],newidx[i],D*newidxPref[i]-queriesa[i-1]-seggyMaxi.get(newidx[i],newidx[i]));
        seggyMini.update(newidx[i],newidx[i],-D*newidxPref[i]+queriesa[i-1]-seggyMini.get(newidx[i],newidx[i]));
        ans = max(ans,seggyMaxi.get(newidx[i],M)+seggyMini.get(1,newidx[i]));
        if(ans&1)cout << ans/2 << ".5 ";
        else cout << ans/2 << ' ';
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41