Submission #1199050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199050		ach00	Meetings (IOI18_meetings)	C++20	17 / 100	75 ms	11592 KiB

meetings

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

struct Node {
    int suffix;
    int prefix;
    int best;
    int l, r;
    Node(int _s, int _p, int _b, int _l, int _r) {
        suffix = _s;
        prefix = _p;
        best = _b;
        l = _l;
        r = _r;
    }

};
const Node ID = Node(0,0,0,-1, -1);
vector<Node> ST;
vector<int> h;
int N,n;

int L(int i) {return 2*i;}
int R(int i) {return 2*i + 1;}
Node merge(Node v1, Node v2) {
    if(v1.l == -1) return Node(v2);
    if(v2.l == -1) return Node(v1);
    int nb = max(v1.suffix + v2.prefix, max(v1.best, v2.best));
    int np = (v1.prefix == v1.r - v1.l + 1) ? (v1.prefix + v2.prefix) : (v1.prefix);
    int ns = (v2.suffix == v2.r - v2.l + 1) ? (v2.suffix + v1.suffix) : (v2.suffix);
    int nl = v1.l;
    int nr = v2.r;
    return Node(ns, np, nb, nl, nr);
}
void build(int i, int l, int r) {
    if(l == r) {
        if(h[l] == 1) {
            ST[i] = Node(1, 1, 1, l, r);
        } else {
            ST[i] = Node(0, 0, 0, l, r);
        }
        return;
    }
    int m = (l+r)/2;
    build(L(i), l, m);
    build(R(i), m+1, r);
    ST[i] = merge(ST[L(i)], ST[R(i)]);
}

Node query(int i, int l, int r, int a, int b) {
    if(l > r || a > r || b < l) return ID;
    if(a <= l && r <= b) return ST[i];
    int m = (l+r)/2;
    return merge(query(L(i), l, m, a, b), query(R(i), m+1, r, a, b));
}



vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    h = H;
    N = n = H.size();
    int Q;
    Q = L.size();
    ST.resize(4*n, ID);
    build(1, 0, n-1);
    vector<ll> ans(Q, -1);
    for(int i = 0; i < Q; i++) {
        Node p = query(1, 0, n-1, L[i], R[i]);
        ll pb = p.best;
        ll r = R[i];
        ll l = L[i];
        ans[i] = 2*(r-l+1) - pb;
    }
    return ans;
}

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