Submission #609551

#	Time	Username	Problem	Language	Result	Execution time	Memory
609551		MohamedAliSaidane	Meetings (IOI18_meetings)	C++14	17 / 100	86 ms	23020 KiB

meetings

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

    typedef long long ll;

    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpi;
    typedef vector<pll> vpl;

    #define pb push_back
    #define popb pop_back
    #define all(x) (x).begin(),(x).end()

    #define ff first
    #define ss second

    const ll INF = 1e18;

    const int nax =  1e5 + 4;
    ll sp[nax][20], A[nax];
    int LG[nax], res[nax];
    int n, q;
    void build()
    {
        for(int i = 0 ; i < n; i++)
            sp[i][0] = res[i];
        for(int j = 1; j < 20; j ++)
            for(int i = 0 ; i + (1 << j) <= n; i ++)
                sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j-1))][j - 1]);
    }
    ll rmq(int l, int r)
    {
        if(l > r)
            return 0;
        int j = LG[r - l + 1];
        return max(sp[l][j], sp[r - (1 << j) + 1][j]);
    }
    vll minimum_costs(vi H, vi L, vi R)
    {
        n = H.size();
        for(int i = 0  ; i < n; i ++)
            A[i] = H[i];
        q = L.size();
        LG[1] = 0 ;
        for(int i= 2; i < nax;i ++)
            LG[i] = LG[i/2] + 1;
        int twos_pref[n + 1];
        twos_pref[0] = 0 ;
        for(int i = 0 ; i < n; i ++)
            twos_pref[i + 1] = twos_pref[i] + (A[i] == 2);
        for(int i = 0 ; i < n;i ++)
        {
            if(A[i] == 2)
            {
                res[i] =  0;
                continue;
            }
            int debut = i;
            int fin = n - 1;
            int rep = i;
            while(debut <= fin)
            {
                int mid = (debut + fin)/2;
                if(twos_pref[mid + 1]- twos_pref[i] == 0)
                {
                    rep = mid ;
                    debut= mid + 1;
                }
                else
                    fin = mid - 1;
            }
            res[i] = rep - i + 1;
        }
        build();
        vll ans(q, INF);
        for(int query = 0; query < q; query ++ )
        {
            int l = L[query];
            int r = R[query];
            int debut = l;
            int fin = r;
            int rep = r + 1;
            while(debut <= fin)
            {
                int mid = (debut + fin)/2;
                if(twos_pref[r + 1] - twos_pref[mid] == 0)
                {
                    rep = mid;
                    fin = mid - 1;
                }
                else
                    debut = mid + 1;
            }
            ll len = r- rep + 1;
            len = max(len, rmq(l, rep - 1));
            ans[query] = len + (r - l + 1 - len) * 2;
        }
        return ans;
    }
    /*
    int32_t main()
    {
        int n, q;
        cin >> n >> q;
        vi H(n), L(q), R(q);
        for(int i = 0 ; i < n;i ++)
            cin >> H[i];
        for(int i = 0; i < q; i ++)
            cin >> L[i] >> R[i];
        vll C = minimum_costs(H, L, R);
        for(auto e: C)
            cout << e << '\n';
    }


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

Compilation message (stderr)

meetings.cpp:121:1: warning: "/*" within comment [-Wcomment]
  121 | /*
      |

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