Submission #83289

#	Time	Username	Problem	Language	Result	Execution time	Memory
83289		7Polygonz	Election (BOI18_election)	C++11	100 / 100	725 ms	52844 KiB

election

using namespace std ;
#include <bits/stdc++.h>
#define TASKNAME "GeneTech"
#define DEBUG(VAL) cerr << #VAL << ": " << VAL << "\n"

const int N = 500000 ;
const int M = 2000000 ;

struct NodeType
{
    int sum , min_surf ;
    NodeType(int _sum = 0 , int _min_surf = 0) :
        sum(_sum) , min_surf(_min_surf) { }

    friend NodeType operator+ (NodeType& shl , NodeType& shr)
    {
        int _sum = shl.sum + shr.sum ;
        int _min_surf = min(shl.min_surf + shr.sum , shr.min_surf) ;
        return NodeType(_sum , _min_surf) ;
    }
} ;
struct QueryType
{
    int right , pos ;
    QueryType(int _right = 0 , int _pos = 0) :
        right(_right) , pos(_pos) { }
} ;

int n , q ;
char gen[N + 1] ;

int a[N] ;
NodeType seg[M] ;
vector < QueryType > queries[N] ;

int answer[N] ;

void Build(int id , int left , int right)
{
    if (right - left < 2) seg[id] = NodeType(1 , 0) ;
    else
    {
        int mid = (left + right) >> 1 ;
        Build(2 * id + 1 , left , mid) ;
        Build(2 * id + 2 , mid , right) ;
        seg[id] = seg[2 * id + 1] + seg[2 * id + 2] ;
    }
}
void Update(int id , int left , int right , int pos , int value)
{
    if (right - left < 2) seg[id] = NodeType(a[left] = value , value) ;
    else
    {
        int mid = (left + right) >> 1 ;
        if (pos < mid) Update(2 * id + 1 , left , mid , pos , value) ;
        else Update(2 * id + 2 , mid , right , pos , value) ;
        seg[id] = seg[2 * id + 1] + seg[2 * id + 2] ;
    }
}
NodeType Query(int id , int left , int right , int bound)
{
    if (right - bound < 2) return seg[id] ;

    int mid = (left + right) >> 1 ;
    if (bound < mid) return Query(2 * id + 1 , left , mid , bound) ;

    NodeType left_query = Query(2 * id + 1 , left , mid , mid - 1) ;
    NodeType right_query = Query(2 * id + 2 , mid , right , bound) ;
    return left_query + right_query ;
}

int main()
{
    // freopen(TASKNAME".inp" , "r" , stdin) ;
    // freopen(TASKNAME".out" , "w" , stdout) ;

    ios::sync_with_stdio(false) ;
    cout.tie(nullptr) ;
    cin.tie(nullptr) ;

    cin >> n >> gen ;
    for (int i = 0 ; i < n ; ++i)
        a[i] = (gen[i] == 'C' ? 1 : -1) ;

    cin >> q ;
    for (int i = 0 ; i < q ; ++i)
    {
        int left , right ;
        cin >> left >> right ;
        queries[--left].emplace_back(--right , i) ;
    }

    Build(0 , 0 , n) ;
    vector < int > my_stack ;
    for (int i = n - 1 ; i >= 0 ; --i)
    {
        if (a[i] < 0) Update(0 , 0 , n , i , 0) , my_stack.push_back(i) ;
        else if (my_stack.size())
        {
            Update(0 , 0 , n , my_stack.back() , -1) ;
            my_stack.pop_back() ;
        }

        for (auto _queries : queries[i])
        {
            int zero_count = upper_bound(my_stack.rbegin() , my_stack.rend() , _queries.right) - my_stack.rbegin() ;
            int negative_count = Query(0 , 0 , n , _queries.right).min_surf ;
            answer[_queries.pos] = zero_count - negative_count ;
        }
    }

    for (int i = 0 ; i < q ; ++i)
        cout << answer[i] << "\n" ;
    return 0 ;
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18