oj.uz

Submission #83289

# Submission time Handle Problem Language Result Execution time Memory
83289 2018-11-06T17:47:01 Z 7Polygonz Election (BOI18_election) C++11
100 / 100
 725 ms 52844 KB 
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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 27768 KB Output is correct
2 Correct 27 ms 28044 KB Output is correct
3 Correct 28 ms 28160 KB Output is correct
4 Correct 29 ms 28160 KB Output is correct
5 Correct 27 ms 28196 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 27768 KB Output is correct
2 Correct 27 ms 28044 KB Output is correct
3 Correct 28 ms 28160 KB Output is correct
4 Correct 29 ms 28160 KB Output is correct
5 Correct 27 ms 28196 KB Output is correct
6 Correct 89 ms 31436 KB Output is correct
7 Correct 76 ms 31872 KB Output is correct
8 Correct 79 ms 32796 KB Output is correct
9 Correct 86 ms 34108 KB Output is correct
10 Correct 90 ms 35156 KB Output is correct
11 Correct 100 ms 36284 KB Output is correct
12 Correct 91 ms 36628 KB Output is correct
13 Correct 90 ms 36888 KB Output is correct
14 Correct 92 ms 36888 KB Output is correct
15 Correct 83 ms 36888 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 27768 KB Output is correct
2 Correct 27 ms 28044 KB Output is correct
3 Correct 28 ms 28160 KB Output is correct
4 Correct 29 ms 28160 KB Output is correct
5 Correct 27 ms 28196 KB Output is correct
6 Correct 89 ms 31436 KB Output is correct
7 Correct 76 ms 31872 KB Output is correct
8 Correct 79 ms 32796 KB Output is correct
9 Correct 86 ms 34108 KB Output is correct
10 Correct 90 ms 35156 KB Output is correct
11 Correct 100 ms 36284 KB Output is correct
12 Correct 91 ms 36628 KB Output is correct
13 Correct 90 ms 36888 KB Output is correct
14 Correct 92 ms 36888 KB Output is correct
15 Correct 83 ms 36888 KB Output is correct
16 Correct 644 ms 51096 KB Output is correct
17 Correct 483 ms 51096 KB Output is correct
18 Correct 581 ms 51096 KB Output is correct
19 Correct 587 ms 51096 KB Output is correct
20 Correct 616 ms 51096 KB Output is correct
21 Correct 725 ms 52528 KB Output is correct
22 Correct 637 ms 52528 KB Output is correct
23 Correct 709 ms 52844 KB Output is correct
24 Correct 691 ms 52844 KB Output is correct
25 Correct 605 ms 52844 KB Output is correct