Submission #1244875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244875		joenpoenmanalt	Meetings (IOI18_meetings)	C++20	0 / 100	3139 ms	30152 KiB

meetings

#include "meetings.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;

typedef int ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

#define ALL(x) begin(x), end(x)

int np2(int n) {
    int N = 1;
    while (N < n) N *= 2;
    return N;
}

const ll maxh = 20;

struct Node {
    ll mx = -1e18;
    ll very_best = 1e18;
    ll best[maxh][maxh]{};
    ll lstart[maxh]{};
    ll rstart[maxh]{};

    Node() {
        for (int h = 0; h < maxh; h++) {
            this->lstart[h] = 0;
            this->rstart[h] = 0;
            for (int h2 = 0; h2 < maxh; h2++) {
                this->best[h][h2] = 1e18;
            }
        }
    }

    Node(int x) {
        this->mx = x;
        this->very_best = x;
        for (int h = 0; h < maxh; h++) {
            this->lstart[h] = max(h, x);
            this->rstart[h] = max(h, x);
            for (int h2 = 0; h2 < maxh; h2++) {
                this->best[h][h2] = 1e18;
            }
        }
        this->best[x][x] = x;
    }
};

Node merge(Node a, Node b) {
    Node r{};
    r.mx = max(a.mx, b.mx);
    for (int h = 0; h < maxh; h++) {
        for (int h2 = 0; h2 < maxh; h2++) {
            r.best[h][h2] = 1e18;
        }
    }
    for (ll h = 0; h < maxh; h++) {
        r.lstart[h] = a.lstart[h] + b.lstart[min(max(h, a.mx), maxh-1)];
        r.rstart[h] = b.rstart[h] + a.rstart[min(max(h, b.mx), maxh-1)];
        for (ll h2 = 0; h2 < maxh; h2++) {
            r.best[h][min(max(h2, b.mx), maxh-1)] = min(r.best[h][min(max(h2, b.mx), maxh-1)], a.best[h][h2] + b.lstart[h2]); 
            r.best[min(max(h2, a.mx), maxh-1)][h] = min(r.best[min(max(h2, a.mx), maxh-1)][h], b.best[h2][h] + a.rstart[h2]); 
        }
    }
    r.very_best = 1e18;
    for (int h = 0; h < maxh; h++) {
        for (int h2 = 0; h2 < maxh; h2++) {
            r.very_best = min(r.best[h][h2], r.very_best);
        }
    }
    return r;
}

vector<Node> tree;

Node query(int l, int r, int a, int b, int k) {
    if (a > r || b < l) return {};
    if (a >= l && b <= r) return tree[k];
    int m = (a+b)/2;
    return merge(query(l, r, a, m, 2*k), query(l, r, m+1, b, 2*k+1));
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
    for (int& x : H) x--;
    int n = H.size();
    int Q = L.size();
    std::vector<long long> C(Q);

    int N = np2(n);
    tree.assign(2*N, {});

    for (int i = 0; i < n; i++) tree[N+i] = Node(H[i]);
    for (int i = N-1; i > 0; i--) tree[i] = merge(tree[2*i], tree[2*i+1]);
    
    for (int i = 0; i < Q; i++) C[i] = query(L[i], R[i], 0, N-1, 1).very_best + R[i] - L[i]+1;

    return C;
}


/*
4 2
2 4 3 5
0 2
1 3

4 1
2 4 3 5
1 3
*/

Compilation message (stderr)

meetings.cpp:22:13: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   22 |     ll mx = -1e18;
      |             ^~~~~
meetings.cpp:23:20: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   23 |     ll very_best = 1e18;
      |                    ^~~~
meetings.cpp: In constructor 'Node::Node()':
meetings.cpp:33:37: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   33 |                 this->best[h][h2] = 1e18;
      |                                     ^~~~
meetings.cpp: In constructor 'Node::Node(int)':
meetings.cpp:45:37: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   45 |                 this->best[h][h2] = 1e18;
      |                                     ^~~~
meetings.cpp: In function 'Node merge(Node, Node)':
meetings.cpp:57:29: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   57 |             r.best[h][h2] = 1e18;
      |                             ^~~~
meetings.cpp:68:19: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   68 |     r.very_best = 1e18;
      |                   ^~~~

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