Submission #759535

#	Time	Username	Problem	Language	Result	Execution time	Memory
759535		pera	Election (BOI18_election)	C++17	0 / 100	284 ms	31572 KiB

election

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

#define int long long

const int N = 5e5 + 1;

vector<int> t(4 * N) , t1(4 * N);

int A = 0 , B = 0;

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 mx(int v , int l , int r , int L , int R){
    if(l > r || r < L || l > R) return INT_MIN;
    if(L <= l && r <= R) return t[v];
    int m = (l + r) / 2;
    return max(mx(v * 2 , l , m , L , R) , mx(v * 2 + 1 , m + 1 , r , L , R));
}

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

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

main(){
    int n;cin >> n;
    string s;cin >> s;
    int k = 0 , l = 0;
    vector<int> cs(n + 1) , ts(n + 1);
    for(int i = n - 1;i > -1;i --){
        k += (s[i] == 'C');
        l += (s[i] == 'T');
        cs[i + 1] = k;
        ts[i + 1] = l;
      //  cout << i << " : ";
    //    cout << cs[i] << " " << ts[i] << endl;
        up2(1 , 1 , n , i , l - k);
    }
    vector<int> C(n + 1) , T(n + 1);
    int c = 0 , t = 0;
    for(int i = 1;i <= n;i ++){
        c += (s[i - 1] == 'C');
        t += (s[i - 1] == 'T');
        C[i] = c;
        T[i] = t;
        up(1 , 1 , n , i , t - c);
    }
    int q;cin >> q;
    while(q --){
        int l , r;cin >> l >> r;
        //cout << x << " " << x1 << endl;
        int ans = 0;
        for(int i = l;i <= r;i ++){
            int x = mx(1 , 1 , n , l , i);
            int x1 = mx2(1 , 1 , n , i + 1 , r);
            x += (C[l - 1] - T[l - 1]);
            x1 -= (ts[r + 1] - cs[r + 1]);
            x = max(x , 0LL) + max(x1 , 0LL);
            ans = max(ans , x);
        }
        //cout << "PAS: ";
        cout << (ans <= 0 ? 0 : ans) << endl;
    }
}

Compilation message (stderr)

election.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main(){
      | ^~~~

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