Submission #759644

#	Time	Username	Problem	Language	Result	Execution time	Memory
759644		pera	Election (BOI18_election)	C++17	0 / 100	13 ms	15964 KiB

election

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 500000 + 1;

vector<int> t(4 * N);

void up(int v , int l , int r , int p , int x){
    if(l == r) t[v] = x;
    else{
        int m = (l + r) / 2;
        if(p <= m) up(v * 2 , l , m , p , x);
        else up(v * 2 + 1 , m + 1 , r , p , x);
        t[v] = max(t[v * 2] , t[v * 2 + 1]);
    }
}

int g(int v , int l , int r , int L , int R){
    if(l > r || l > R || r < L) return INT_MIN;
    if(L <= l && r <= R) return t[v];
    return max(g(v * 2 , l , (l + r) / 2 , L , R) , g(v * 2 + 1 , (l + r) / 2 + 1 , r , L , R));
}

main(){
    int n;cin >> n;
    string S;cin >> S;
    vector<int> p(n + 2) , s(n + 2) , r1(n + 2) , r2(n + 2);
    int x = 0 , y = 0;
    for(int i = 0;i < S.size();i ++){
        x += (S[i] == 'C');
        y += (S[i] == 'T');
        p[i + 1] = r1[i + 1] = (y - x);
       // if(i) p[i + 1] = max(p[i + 1] , p[i]);
    }
    x = y = 0;
    for(int i = S.size() - 1;i > -1;i --){
        x += (S[i] == 'C');
        y += (S[i] == 'T');
        s[i + 1] = r2[i + 1] = (y - x);
        //if(i + 2 <= n)s[i + 1] = max(s[i + 1] , s[i + 2]);
    }
    for(int i = 1;i <= n;i ++){
    //    cout << "I: " << p[i] << " " << s[i] << endl;
        p[i] = max(0LL , p[i]);
        s[i + 1] = max(0LL , s[i + 1]);
        up(1 , 1 , n , i , p[i] + s[i + 1]);
    }
    int q;cin >> q;
    while(q --){
        int l , r;cin >> l >> r;
        int x = g(1 , 1 , n , l , r) - r1[l - 1] - r2[r + 1];
        //cout << "PAS: ";
        cout << min(x , r - l + 1) << endl;
    }
}

Compilation message (stderr)

election.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~
election.cpp: In function 'int main()':
election.cpp:31:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0;i < S.size();i ++){
      |                   ~~^~~~~~~~~~

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