QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497627#8783. Cherry Pickinglulujia5454#WA 1ms5680kbC++203.1kb2024-07-29 15:18:202024-07-29 15:18:20

Judging History

你现在查看的是最新测评结果

  • [2024-07-29 15:18:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5680kb
  • [2024-07-29 15:18:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int a[N], f[N];
vector<int> v[N]; set<pair<pair<int, int>, int>> st;
void solve()
{

    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        v[a[i]].push_back(i);
    }
    string s;
    cin >> s;
    s = " " + s;
   
    int l = 0, r = -1;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '1')
        {
            if (l == 0)
                l = r = i;
            else
                r++;
        }
        else
        {
            if (r >= l)
            {
                st.insert({{l, r}, r - l + 1});
                f[r - l + 1]++;
                l = 0;
                r = -1;
            }
        }
      // cout<<l<<' '<<r<<endl;
    }
    if (r >= l)
    {
        st.insert({{l, r}, r - l + 1});
        f[r - l + 1]++;
    }
    int maxx = 0;
    for (int i = 0; i < 1e5; i++)
    {
        for (auto ff : v[i])
        {
            //cout<<ff<<endl;
            if (s[ff] == '1')
            {
                auto tt = st.upper_bound({{ff, 1e9}, 0});
                if (tt != st.end())
                {
                    tt--;
                    auto ttt = *tt;
                    f[ttt.second]--;
                    ttt.second--;
                    f[ttt.second]++;
                    st.erase(tt);
                    st.insert(ttt);
                }
            }
            else
            {
                auto tt = st.lower_bound({{ff, ff}, 0});
                if (tt != st.end())
                {
                    auto ttt = *tt;
                    if (ttt.first.first - 1 == ff)
                    {
                        st.erase(ttt);
                        ttt.first.first--;
                        st.insert(ttt);
                    }
                    else
                    {
                        st.insert({{ff, ff}, 0});
                    }
                }
                else
                    st.insert({{ff, ff}, 0});
                tt = st.lower_bound({{ff, ff}, 0});
                if (tt != st.begin())
                {
                    auto ttt = tt;
                    tt--;
                    auto ttt1 = *ttt, tt1 = *tt;
                    if (ttt1.first.second + 1 == tt1.first.first)
                    {
                        f[ttt1.second]--;
                        f[tt1.second]--;
                        st.erase(ttt);
                        st.erase(tt);
                        f[ttt1.second + tt1.second]++;
                        st.insert({{tt1.first.first, ttt1.first.second}, ttt1.second + tt1.second});
                    }
                }
            }
        }
        if (f[k])
        {
            maxx = min(n,i+1);
        }
    }
    cout << maxx << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3604kb

input:

5 2
1 2 3 4 5
01101

output:

2

result:

ok answer is '2'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5680kb

input:

5 2
3 4 5 2 1
10101

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

1 1
1
1

output:

1

result:

ok answer is '1'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3856kb

input:

1 1
1
0

output:

0

result:

ok answer is '0'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 5616kb

input:

5 3
8 3 5 2 7
10101

output:

0

result:

wrong answer expected '5', found '0'