Submission #1209378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209378		anfi	Nile (IOI24_nile)	C++20	17 / 100	2095 ms	2162688 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using int64 = long long;
#define pi pair<int64, int64>
#define artefak pair<pi, pi>
const int64 inf = -(1 << 40);
const int64 mxn = (1 << 18);
int64 tree[4*mxn];

void update(int n, int l, int r, int idx, int val){
    if(l == r){
        tree[n] = val;
        return;
    }
    int m = (l+r)/2;
    if(idx <= m){
        update(2*n+1, l, m, idx, val);
    }else update(2*n+2, m+1, r, idx, val);
    tree[n] = max(tree[2*n+1], tree[2*n+2]);
}

int64 query(int n, int lf, int rg, int l, int r){
    if(r < lf || rg < l) return inf;
    if(lf <= l && rg <= r) return tree[n];
    int mid = (lf+rg)/2;
    return max(query(2*n+1, lf, mid, l, r), query(2*n+2, mid+1,rg, l,r));
}

vector<int64> calculate_costs(vector<int> w,vector<int> a, vector<int> b, vector<int> e){
    int n = w.size(), q = e.size();
    if(n == 0){
        return vector<int64>(q, 0);
    }
    int sigma_a = 0;
    vector<artefak> item;
    for(int i = 0;i < n; i++){
        sigma_a += a[i];
        item.push_back({{w[i], a[i]}, {b[i], a[i]-b[i]}});
    }
    bool cek = 1;
    sort(item.begin(), item.end());
    for(auto &lo : item){
        if(lo.fi.se != 2 || lo.se.fi != 1){
            cek = 0;
            break;
        }
    }
    vector<int64> ans;
    if(cek){
        for(int d : e){
            vector<int> dp(n);
            int j = 0;
            for(int i = 1; i <n; i++){
                while(j < i && item[j].fi.fi < item[i].fi.fi-d) j++;
                int ambil = 0;
                if(j <= i-1){
                    ambil = dp[i] = 1+(i-2>=0 ? dp[i-2] : 0);
                }
                dp[i] = max(dp[i-1], ambil);
            }
            int m = dp[n-1];
            ans.push_back(2*n-2*m);
        }
        return ans;
    }

    for(int i = 0; i < q; i++){
        int d = e[i];
        fill(tree, tree+4*n, inf);
        update(0, 0, n-1, 0, item[0].se.se);
        vector<int64> dp(n);
        for(int j = 1; j < n; j++){
            int W = item[j].fi.fi;
            int minw = W-d;
            int l = 0, r = j;
            while(l < r){
                int mid = (l+r)>>1;
                if(item[mid].fi.fi < minw) l = mid+1;
                else r = mid;
            }
            int jnt = l;

            int64 ambil = inf;
            if(jnt <= j-1){
                ambil = item[j].se.se+query(0,0,n-1, jnt, j-1);
            }
            dp[j] = dp[j-1];
            if(ambil >= -1e15) dp[j] = max(dp[j], ambil);
            int64 val = item[j].se.se+dp[j-1];
            update(0,0,n-1,j,val);
        }
        int64 sav = dp[n-1];
        int64 cost = sigma_a-sav;
        ans.push_back(cost);
    }
    return ans;
}

Compilation message (stderr)

nile.cpp:9:23: warning: left shift count >= width of type [-Wshift-count-overflow]
    9 | const int64 inf = -(1 << 40);
      |                     ~~^~~~~

• 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