Submission #781391

#	Time	Username	Problem	Language	Result	Execution time	Memory
781391		vjudge1	Meetings (IOI18_meetings)	C++17	0 / 100	1 ms	212 KiB

meetings

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

#define ll long long
#define ALL(x) x.begin(), x.end()

// solving subtask 1 + 2 in O(N^2 + QN) time
const ll LLINF = 1ll<<60;
const int maxn = 1e5 + 10;
int n, q, tree[maxn * 4] = {0};
vector<int> two;

void update(int x, int v, int tl = 0, int tr = maxn, int i = 1){
    if (tl > x || tr < x) return;
    if (tl == tr){
        tree[i] = v; return;
    }
    int tm = (tl + tr) / 2;
    update(x, v, tl, tm, i * 2); update(x, v, tm + 1, tr, i * 2 + 1);
    tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}

int query(int l, int r, int tl = 0, int tr = maxn, int i = 1){
    if (l > tr || tl > r) return 0;
    if (l <= tl && tr <= r) return tree[i];
    int tm = (tl + tr) / 2;
    return max(query(l, r, tl, tm, i * 2), 
    query(l, r, tm + 1, tr, i * 2 + 1));
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
    n = H.size();
    int last = -1; two.push_back(-1);
    for (int i = 1; i < n; i++){
        if (H[i] == 2){
            update(last, i - last - 1);
            last = i; two.push_back(last);
        }
    }
    update(last, n - last - 1);
    two.push_back(last); two.push_back(n);
    q = L.size();
    vector<ll> c(q);
    for (int i = 0; i < q; i++){
        int l = lower_bound(ALL(two), L[i] - 1) - two.begin();
        int r = upper_bound(ALL(two), R[i] + 2) - two.begin() - 2;
        l = two[l], r = two[r];
        int mx = query(l, r); 
        l = min(l, R[i] + 1); r = max(r, L[i] - 1);
        mx = max({mx, l - L[i], R[i] - r});
        // cout << mx << ' ' << l << ' ' << r << endl;
        c[i] = (R[i] - L[i] + 1) * 2 - mx;
    }
    return c;
}

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