Submission #1079185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079185		MrPavlito	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	0 ms	348 KiB

ho_t2

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
//#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;

signed main()
{
    //ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    ///cin >> tt;
    while(tt--)
    {
        int n,k;
        cin >> n >> k;
        vector<int>jpref(n+1,0);
        vector<int>ipref(n+1,0);
        vector<int>opref(n+1,0);
        vector<int>svij;
        vector<int>svio;
        string s;cin >> s;
        for(int i=0; i<n; i++)
        {
            if(s[i] == 'O')opref[i+1] ++;
            else if(s[i] == 'J')
            {
                jpref[i+1] ++;
                svij.pb(i);
            }
            opref[i+1] += opref[i];
            jpref[i+1] += jpref[i];
        }
        for(int i=n-1; i>=0; i--)
        {
            if(s[i] == 'I')ipref[i]++;
            ipref[i]+= ipref[i+1];
        }
        int rez = inf;
        int jpointer = 0;
        for(int i=0; i<n; i++)
        {
            if(s[i]!= 'J' || jpref[i+1] >= k)
            {
                int l = i+1; int r = n-1;int p = inf;
                while(l<=r)
                {
                    int mid = l+r>>1;
                    bool b1 = ipref[mid] >= k;
                    bool b2 = opref[mid] - opref[i] >=k;
                    if(b1 && b2)
                    {
                        p = mid;
                        r = mid-1;
                    }
                    else if(b1)l = mid+1;
                    else if(b2)r = mid-1;
                    else break;
                }
                if(p == inf)continue;
                int trazi = ipref[p] - k+1;
                l = p, r = n-1;
                while(l<=r)
                {
                    int mid = l+r>>1;
                    if(ipref[mid] >= trazi)
                    {
                        l = mid+1;
                        p = mid;
                    }
                    else r = mid-1;
                }
                rez = min(rez, p-jpointer-1-3*k+2);
            }
        }
        if(rez== inf)cout << -1 << endl;
        else cout << rez << endl;
    }
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:57:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |                     int mid = l+r>>1;
      |                               ~^~
ho_t2.cpp:74:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |                     int mid = l+r>>1;
      |                               ~^~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87