Submission #1235148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235148		ricardsjansons	Nile (IOI24_nile)	C++20	17 / 100	2095 ms	223004 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n;
vector<int>w;

const int N=1<<17;
int segt[N*2]{};

void upd(int i,int dw){
    i+=N;
    segt[i]=dw;
    for(i/=2;i;i/=2){
        segt[i]=max(segt[i*2],segt[i*2+1]);
    }
}

map<pair<int,int>,int>mem;
int maxdw(int l,int r,bool x=1){
    if(x){
        l+=N;
        r+=N;
    }
    if(mem.count({l,r})){
        return mem[{l,r}];
    }
    int&res=mem[{l,r}];
    if(l<=r){
        if(l%2==1){
            res=max(res,segt[l++]);
        }
        if(r%2==0){
            res=max(res,segt[r--]);
        }
        l/=2;
        r/=2;
    }
    res=max(res,maxdw(l,r,0));
    return res;
}

ll f(int d){
    ll res=0;
    for(int i=0,j=0;i<n;i=++j){
        int l=i+1,r=n-1;
        while(l<r){
            int mid=(l+r+1)/2;
            if(maxdw(i,mid)<=d){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        j=l;
        if(j==i+1&&w[j]-w[i]>d){
            j=i;
        }
        res+=j-i+1;
        if((j-i)%2==0){
            res++;
        }
    }
    return res;
}

vector<ll> calculate_costs(vector<int>W,vector<int>A,vector<int>B,vector<int>E) {
    n=A.size();
    sort(W.begin(),W.end());
    w=W;
    for(int i=1;i<n;i++){
        upd(i,w[i]-w[i-1]);
    }
    vector<ll>r;
    for(int d:E){
        r.push_back(f(d));
    }
    return r;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18