oj.uz

Submission #96563

# Submission time Handle Problem Language Result Execution time Memory
96563 2019-02-10T10:19:18 Z josiftepe Election (BOI18_election) C++14
100 / 100
 1824 ms 58528 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxn = 5e5 + 10;
int n;
string s;
bool visited[maxn];
int arr[maxn];
int solve(int S, int E){
    int balance = 0;
    int ret = 0;
    memset(visited, false, sizeof visited);
    for(int i = S; i <= E; i ++){
        if(s[i] == 'C'){
            balance ++;
            arr[i] = 1;
        }
        else{
            balance --;
            arr[i] = -1;
        }

        if(balance < 0){
            balance = 0;
            visited[i] = true;
           // arr[i] = 0;
            ret ++;
        }

    }
    int suff_sum = 0;
    int mnn = (1 << 30);
    for(int i = S; i <= S; i ++){
        suff_sum += arr[i];
    //    mnn = min(mnn, min(0, -suff_sum));
    }
    balance = 0;
    for(int i = E; i >= S; i --){
        if(s[i] == 'C'){
            balance ++;
        }
        else if(!visited[i] and s[i] == 'T'){
            balance --;
        }
      //  cout << balance << " " ;
        mnn = min(mnn, min(0, -balance));
        if(balance < 0){
            balance = 0;
//            ret ++;
        }
    }
    return ret + abs(mnn);
}
struct elem{
    int L, R, sum, min_suf;
    elem(){
        L = R = sum = min_suf = 0;
    }
};
elem mymerge(elem A, elem B){
    elem ret;
    ret.R = max(A.R, B.R - A.min_suf);
    ret.sum = max(B.sum, A.sum - B.min_suf);
    ret.min_suf = A.min_suf + B.min_suf;
    ret.L = max(max(A.L - B.min_suf, B.L - A.min_suf), A.R + B.sum);
    return ret;
}
class node{
public:
    elem val;
    int lb, rb;
    node *left, *right;
    node(int levo, int desno){
        lb = levo;
        rb = desno;
        if(levo == desno){
            if(s[levo] == 'T'){
                val.L = val.R = val.sum = 1;
                val.min_suf = -1;
            }
            else{
                val.L = val.R = val.sum = 0;
                val.min_suf = 1;
            }
        }
        else{
            int mid = (levo + desno) >> 1;
            left = new node(levo, mid);
            right = new node(mid + 1, desno);
            val = mymerge(left -> val, right -> val);
        }

    }
    elem query(int i, int j){
        if(i <= lb and rb <= j){
            return val;
        }
        /// i j l r i j
        if(j < lb or rb < i){
            return elem();
        }
        return mymerge(left -> query(i, j), right -> query(i, j));
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    //ifstream cin("in.txt.txt");
    cin >> n >> s;
    int q;
    cin >> q;
    node *root = new node(0, n - 1);
    for(int i = 0; i < q; i ++){
        int a, b;
        cin >> a >> b;
        a --;
        b --;
        cout << root -> query(a, b).L << endl;
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 508 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 508 KB Output is correct
6 Correct 195 ms 8204 KB Output is correct
7 Correct 160 ms 8312 KB Output is correct
8 Correct 172 ms 8184 KB Output is correct
9 Correct 180 ms 8184 KB Output is correct
10 Correct 202 ms 8068 KB Output is correct
11 Correct 193 ms 8376 KB Output is correct
12 Correct 179 ms 8312 KB Output is correct
13 Correct 185 ms 8312 KB Output is correct
14 Correct 187 ms 8184 KB Output is correct
15 Correct 203 ms 8348 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 508 KB Output is correct
6 Correct 195 ms 8204 KB Output is correct
7 Correct 160 ms 8312 KB Output is correct
8 Correct 172 ms 8184 KB Output is correct
9 Correct 180 ms 8184 KB Output is correct
10 Correct 202 ms 8068 KB Output is correct
11 Correct 193 ms 8376 KB Output is correct
12 Correct 179 ms 8312 KB Output is correct
13 Correct 185 ms 8312 KB Output is correct
14 Correct 187 ms 8184 KB Output is correct
15 Correct 203 ms 8348 KB Output is correct
16 Correct 1813 ms 57660 KB Output is correct
17 Correct 1447 ms 57104 KB Output is correct
18 Correct 1546 ms 57612 KB Output is correct
19 Correct 1470 ms 56812 KB Output is correct
20 Correct 1824 ms 56848 KB Output is correct
21 Correct 1767 ms 58316 KB Output is correct
22 Correct 1824 ms 58304 KB Output is correct
23 Correct 1763 ms 58528 KB Output is correct
24 Correct 1814 ms 58008 KB Output is correct
25 Correct 1741 ms 57780 KB Output is correct