General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
96215681 Practice:
trycod3
1430D - 8 GNU C++17 Wrong answer on test 2 15 ms 144 KB 2020-10-21 10:45:32 2020-10-21 10:45:32
 
 
→ Source
#include <bits/stdc++.h>

#define ll long long int
#define F first
#define S second
#define FOR(i , begin , step , end) for(ll i = begin ; i <= end ; i+=step)
#define LOOP(i , begin , step , end , arr) for(ll i = begin ; i <= end ; i+=step) { cout << arr[i] << " "; } cout << endl;
#define lengall(s) s.size()
#define see(a) cout << a << endl;
#define debug(a) cout << (#a) << " = " << a << "\n";
#define line(a) cout << a << " " ;
#define space(a , b) cout << a << " " << b << endl;
#define REN(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define MAXX 1000007

using namespace std;

struct box {
    ll data, idx;
};

vector <box> seg;
ll sz = 1;

box Imerge(box l, box r)
{
    box res;
    if(l.data == r.data) {
        res.data = l.data;
        if(l.idx > r.idx) {
            res.idx = l.idx;
        } else {
            res.idx = r.idx;
        }
    } else {
        if(l.data > r.data) {
            res.data = l.data;
            res.idx = l.idx;
        } else {
            res.data = r.data;
            res.idx = r.idx;
        }
    }
    return res;
}

void build(ll i, ll val, ll node, ll lx, ll rx)
{
    if(rx == lx) {
        seg[node] = {val, i};
        return;
    }
    ll mx = (lx + rx) >> 1;
    if(i <= mx) {
        build(i, val, node * 2 + 1, lx, mx);
    } else {
        build(i, val, node * 2 + 2, mx + 1, rx);
    }
    seg[node] = Imerge(seg[node * 2 + 1], seg[node * 2 + 2]);
}

int main()
{
    ll t;
    cin >> t;
    while(t--) {

        ll n;
        string s;
        cin >> n;
        cin >> s;

        s += "$";

        n = s.size();

        ll step = 1;
        vector <ll> pre;

        FOR(i, 0, 1, n - 2) {
            if(s[i] == s[i + 1]) {
                step++;
            } else {
                pre.push_back(step);
                step = 1;
            }
        }

        while(sz < n - 1) {
            sz <<= 1;
        }
        seg.assign(sz << 1, {0ll, 0ll});

        FOR(i, 0, 1, lengall(pre) - 1) {
            build(i, pre[i], 0, 0, sz - 1);
        }

        ll mx = 0;

        FOR(i, 0, 1, lengall(pre) - 1) {
            if(pre[i] == 1) {
                mx++;
                pre[ i ] = -1;
                build(i, pre[i], 0, 0, sz - 1);
                pre[ seg[0].idx ]--;
                build(seg[0].idx, pre[seg[0].idx], 0, 0, sz - 1);
            } else if(pre[i] > 1){
                mx++;
                pre[i] = -1;
                build(i, pre[i], 0, 0, sz - 1);
            }
        }



        see(mx)

    }


    return 0;
}

 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details