Submission #250089

#	Time	Username	Problem	Language	Result	Execution time	Memory
250089		ant101	Meetings (IOI18_meetings)	C++14	36 / 100	865 ms	392568 KiB

meetings

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
#include "meetings.h"
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)
typedef long long ll;

const ll infty = 1000000000;

struct info_t {
    int best;
    int le,ri,len;
    info_t() : best(0), le(0), ri(0), len(0) { }
};

info_t single(int val) {
    info_t I;
    I.best = I.le = I.ri = val == 1;
    I.len = 1;
    return I;
}

info_t join(const info_t& L, const info_t& R) {
    info_t I;
    I.best = max(max(L.best, R.best), L.ri + R.le);
    I.le = L.le;
    if (L.best == L.len)
        I.le = max(I.le, L.len + R.le);
    I.ri = R.ri;
    if (R.best == R.len)
        I.ri = max(I.ri, L.ri + R.len);
    I.len = L.len + R.len;
    return I;
}

struct tree_t {
    vector<info_t> tree;
    int base;
    int n;
    
    tree_t(const vector<int>& vals) {
        n = vals.size();
        base = 1;
        while (base < n) { base *= 2; }
        tree.resize(2*base);
        REP(i, n) {
            tree[base + i] = single(vals[i]);
        }
        for (int i = base-1; i >= 1; i--) {
            tree[i] = join(tree[2*i], tree[2*i+1]);
        }
    }
    
    void update(int x, int val) {
        x += base;
        tree[x] = single(val);
        while (x > 1) {
            x /= 2;
            tree[x] = join(tree[2*x], tree[2*x+1]);
        }
    }
    
    info_t query(int xl, int xr) {
        xl += base;
        xr += base;
        if (xl == xr) {
            return tree[xl];
        }
        info_t IL = tree[xl], IR = tree[xr];
        while (xl/2 != xr/2) {
            if (~xl&1) { IL = join(IL, tree[xl+1]); }
            if (xr&1) { IR = join(tree[xr-1], IR); }
            xl /= 2;
            xr /= 2;
        }
        return join(IL, IR);
    }
};


vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    if (L.size() <= 5000) {
        int N = H.size();
        int Q = L.size();
        vector<ll> C(Q);
        
        vector<vector<ll> > cost_le(N, vector<ll>(N)), cost_ri(N, vector<ll>(N));
        REP(x, N) {
            ll cost = 0;
            int maxh = H[x];
            for (int k = x-1; k >= 0; k--) {
                maxh = max(maxh, H[k]);
                cost += maxh;
                cost_le[x][k] = cost;
            }
            cost = 0;
            maxh = H[x];
            for (int k = x+1; k < N; k++) {
                maxh = max(maxh, H[k]);
                cost += maxh;
                cost_ri[x][k] = cost;
            }
        }
        
        REP(i, Q) {
            ll ans = infty * N;
            for (int x = L[i]; x <= R[i]; x++) {
                ll cost = cost_le[x][L[i]] + H[x] + cost_ri[x][R[i]];
                ans = min(ans, cost);
            }
            C[i] = ans;
        }
        
        return C;
    }
    int Q = L.size();
    vector<ll> C(Q);
    
    tree_t tree(H);
    REP(i, Q) {
        int size = tree.query(L[i], R[i]).best;
        C[i] = 2*(R[i] + 1 - L[i]) - size;
    }
    
    return C;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40