Submission #604558

#	Time	Username	Problem	Language	Result	Execution time	Memory
604558		cheissmart	Meetings (IOI18_meetings)	C++14	0 / 100	604 ms	36148 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 750005;

int h[N], l[N], r[N], n, q;
ll ans[N];
int lst[N][22], nxt[N][22];
int lst_geq[N][22], nxt_geq[N][22];
V<pi> G[N];

ll t[N * 4], lz[N * 4];
void apply(int v, ll x) {
    t[v] += x;
    lz[v] += x;
}
void push(int v) {
    apply(v * 2, lz[v]);
    apply(v * 2 + 1, lz[v]);
    lz[v] = 0;
}
void upd(int l, int r, int x, int v = 1, int tl = 1, int tr = n + 1) {
    if(l <= tl && tr <= r) {
        apply(v, x);
        return;
    }
    push(v);
    int tm = (tl + tr) / 2;
    if(l < tm) upd(l, r, x, v * 2, tl, tm);
    if(r > tm) upd(l, r, x, v * 2 + 1, tm, tr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}
ll qry(int l, int r, int v = 1, int tl = 1, int tr = n + 1) {
    if(l <= tl && tr <= r) return t[v];
    push(v);
    int tm = (tl + tr) / 2;
    ll res = 1e18;
    if(l < tm) res = min(res, qry(l, r, v * 2, tl, tm));
    if(r > tm) res = min(res, qry(l, r, v * 2 + 1, tm, tr));
    return res;
}

void solve() { 
    for(int i = 0; i < q; i++)
        G[r[i]].EB(l[i], i);
    for(int i = 0; i < n; i++) {
        for(int j = 1; j <= 21; j++)
            lst[i][j] = i - 1 >= 0 ? lst[i - 1][j] : -1;
        lst[i][h[i]] = i;
    }
    for(int i = n - 1; i >= 0; i--) {
        for(int j = 1; j <= 21; j++)
            nxt[i][j] = i + 1 < n ? nxt[i + 1][j] : n;
        nxt[i][h[i]] = i;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 21; j >= 1; j--) {
            lst_geq[i][j] = lst[i][j];
            if(j + 1 <= 21) lst_geq[i][j] = max(lst_geq[i][j], lst_geq[i][j + 1]);
            nxt_geq[i][j] = nxt[i][j];
            if(j + 1 <= 21) nxt_geq[i][j] = min(nxt_geq[i][j], nxt_geq[i][j + 1]);
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 1; j <= 20; j++) {
            if(nxt[i][j] < n) {
                int lb = max(nxt[i][j], i + 1), rb = nxt_geq[i][j + 1] - 1;
                if(lb > rb) continue;
                upd(lb, rb + 1, j);
            }
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 1; j <= 20; j++)
            if(lst[i][j] >= 0) {
                int rb = lst[i][j], lb = lst_geq[i][j + 1] + 1;
                if(lb > rb) continue;
                upd(lb, rb + 1, j);
            }

        for(auto[j, qi]:G[i]) {
            V<array<int, 3>> todo;
            if(j) {
                for(int k = 1; k <= 20; k++) {
                    int rb = lst[j - 1][k], lb = lst_geq[j - 1][k + 1] + 1;
                    int small = j - 1 - rb, same = max(rb - lb + 1, 0);
                    int lbb = nxt[j][k], rbb = nxt_geq[j][k + 1] - 1;
                    if(j < nxt_geq[j][k]) todo.PB({j, nxt_geq[j][k], same * k});
                    if(lbb <= rbb) todo.PB({lbb, rbb + 1, (small + same) * k});
                }
            }
            for(auto[lb, rb, x]:todo)
                upd(lb, rb, -x);
            ans[qi] = qry(j, i + 1);
            for(auto[lb, rb, x]:todo)
                upd(lb, rb, x);
        }
    }
}

V<ll> minimum_costs(vi _h, vi _l, vi _r) {
    n = SZ(_h), q = SZ(_l);
    for(int i = 0; i < n; i++) h[i] = _h[i];
    for(int i = 0; i < q; i++) l[i] = _l[i], r[i] = _r[i];
    solve();
    V<ll> tt;
    for(int i = 0; i < q; i++)
        tt.PB(ans[i]);
    return tt;
}

Compilation message (stderr)

meetings.cpp: In function 'void solve()':
meetings.cpp:97:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |         for(auto[j, qi]:G[i]) {
      |                 ^
meetings.cpp:108:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |             for(auto[lb, rb, x]:todo)
      |                     ^
meetings.cpp:111:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |             for(auto[lb, rb, x]:todo)
      |                     ^

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