Submission #944988

#	Time	Username	Problem	Language	Result	Execution time	Memory
944988		gelastropod	Meetings (IOI18_meetings)	C++14	0 / 100	556 ms	786432 KiB

meetings

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

struct node
{
    int s, e, m, v;
    node *l, *r;

    node (int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(-1)
    {
        if (s != e)
            l = new node(s, m),
            r = new node(m + 1, e);
    }

    void upd(int n, int x)
    {
        if (s == e)
        {
            v = x;
            return;
        }
        if (n <= m)
            l->upd(n, x);
        else
            r->upd(n, x);
        v = max(l->v, r->v);
    }

    int qry(int a, int b)
    {
        if (b < s || a > e)
            return -1;
        if (a <= s && b >= e)
            return v;
        return max(l->qry(a, b), r->qry(a, b));
    }
} *root;

vector<long long> minimum_costs(vector<signed> H, vector<signed> L,
                                vector<signed> R) {
    int N = H.size(), Q = L.size();
    stack<int> stk;
    vector<pair<int, int>> ranges;
    vector<int> l, r;
    bool done = false;
    for (int i = 0; i < N; i++)
    {
        if (H[i] == 1)
        {
            if (!done)
            {
                ranges.push_back(pair<int, int>(i, i));
                done = true;
            }
            else
            {
                ranges[ranges.size() - 1].second = i;
            }
        }
        else
        {
            done = false;
        }
    }
    root = new node(0, ranges.size() - 1);
    for (int i = 0; i < ranges.size(); i++)
    {
        root->upd(i, ranges[i].second + 1 - ranges[i].first);
        l.push_back(ranges[i].first);
        r.push_back(ranges[i].second);
    }
    vector<int> ans;
    for (int i = 0; i < Q; i++)
    {
        int an = INT_MAX;
        auto iter1 = upper_bound(l.begin(), l.end(), L[i]);
        if (iter1 != l.begin())
        {
            iter1--;
            auto iter2 = lower_bound(r.begin(), r.end(), L[i]);
            if (iter2 != r.end() && iter1 == iter2)
            {
                an = min(an, *iter2 - L[i] + 1);
            }
        }
        iter1 = upper_bound(l.begin(), l.end(), R[i]);
        if (iter1 != l.begin())
        {
            iter1--;
            auto iter2 = lower_bound(r.begin(), r.end(), R[i]);
            if (iter2 != r.end() && iter1 == iter2)
            {
                an = min(an, R[i] - *iter1 + 1);
            }
        }
        iter1 = lower_bound(r.begin(), r.end(), L[i]);
        auto iter2 = upper_bound(l.begin(), l.end(), R[i]);
        if (iter2 != l.begin())
        {
            an = min(an, root->qry(distance(r.begin(), iter1), distance(l.begin(), iter2)));
        }
        ans.push_back((R[i] + 1 - L[i]) * 2 - an);
    }
    return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:69:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0; i < ranges.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~

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