Submission #999323

#	Time	Username	Problem	Language	Result	Execution time	Memory
999323		amine_aroua	Meetings (IOI18_meetings)	C++17	0 / 100	1 ms	348 KiB

meetings

#include<bits/stdc++.h>
using namespace std;
#define intt long long
#define pb push_back
#define forr(i , x , y) for(int i = x; i <= y;i++)
#define fore(i , n) for(int i = 0 ; i < n;i++)
#define forn(i ,x , y) for(int i = x ; i >= y;i--)
namespace {

    int read_int() {
        int x;
        if (scanf("%d", &x) != 1) {
            fprintf(stderr, "Error while reading input\n");
            exit(1);
        }
        return x;
    }

}  // namespace
const intt INF =  1e18;
struct segTree
{
    int BASE;
    vector<int> tree;
    segTree(int n , vector<int> &temp)
    {
        BASE = n;
        while(__builtin_popcount(BASE) != 1)
            BASE++;
        tree.assign(2*BASE , 0);
        fore(i , n)
            tree[i + BASE] = temp[i];
        forn(i , BASE - 1 , 0)
            tree[i] = max(tree[2*i] , tree[2*i + 1]);
    }
    int query(int l , int r)
    {
        l+=BASE;
        r+=BASE;
        if(l == r)
            return tree[l];
        int lt = tree[l] , rt = tree[r];
        while (l +1 < r)
        {
            if(l%2 == 0)
            {
                lt = max(lt ,  tree[l + 1]);
            }
            if(r%2 == 1)
                rt = max(tree[r - 1] , rt);
            l>>=1;
            r>>=1;
        }
        return max(lt , rt);
    }
};
vector<long long> minimum_costs(vector<int> H, vector<int> L , vector<int> R)
{
    int n = (int)H.size();
    fore(i , n)
        H[i]--;
    int q = (int)L.size();
    vector<int> nxt(n + 2) , prv(n + 1) , temp(n);
    prv[0] = 0;
    nxt[n + 1] = n + 1;
    forr(i , 1 , n)
    {
        if(H[i - 1] == 1)
            prv[i] = i;
        else
            prv[i] = prv[i - 1];
    }
    forn(i , n , 1)
    {
        if(H[i - 1] == 1)
            nxt[i] = i;
        else
            nxt[i] = nxt[i + 1];
    }
    forr(i , 0 , n - 1)
    {
        temp[i] = nxt[i + 1] - prv[i + 1];
    }
    segTree seg(n , temp);
    vector<intt> ans(q , INF);
    fore(i , q)
    {
        int l = L[i] , r = R[i];
        if(nxt[l + 1] > r + 1)
            ans[i] = 0;
        else
        {
            int val = 0;
            int _l = nxt[l + 1] - 1, _r = prv[r + 1] - 1;
            if(H[r] == 0)
                ans[i] = min(ans[i] , (1LL)*(_r - l + 1));
            if(H[l] == 0)
                ans[i] = min(ans[i] , (1LL) * (r - _l + 1));
            val = max(val  , seg.query(_l , _r));
            ans[i] = min({ans[i] , 1LL * (r - l + 1) , 1LL * (r - l + 2 - val)});
        }
    }
    return ans;
}

Compilation message (stderr)

meetings.cpp:10:9: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
   10 |     int read_int() {
      |         ^~~~~~~~

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