oj.uz

답안 #151863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
151863 2019-09-05T07:08:56 Z Knps4422 Election (BOI18_election) C++
0 / 100
 10 ms 504 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n, q;
int s[500005];
int st1[2000005],st2[2000005];
int p1[500005],p2[500005];
vector <int> vec;
void build1(int nod , int l , int r){
    if(l == r){
        st1[nod] = p1[l];
    }else{
        int mid = (l+r)/2;
        build1(nod*2,l,mid);
        build1(nod*2+1,mid+1,r);
        st1[nod] = max(st1[nod*2],st1[nod*2+1]);
    }
}
void build2(int nod , int l , int r){
    if(l == r){
        st2[nod] = p2[l];
    }else{
        int mid = (l+r)/2;
        build2(nod*2,l,mid);
        build2(nod*2+1,mid+1,r);
        st2[nod] = max(st2[nod*2],st2[nod*2+1]);
    }
}
int query1(int nod , int l , int r , int lt , int rt){
    if(l > r)return 0;
    if(l >= lt && r <= rt)return st1[nod];
    int mid = (l+r)/2;
    return max(query1(nod*2,l,mid,lt,rt),query1(nod*2+1,mid+1,r,lt,rt));
}
int query2(int nod , int l , int r , int lt , int rt){
    if(l > r)return 0;
    if(l >= lt && r <= rt)return st2[nod];
    int mid = (l+r)/2;
    return max(query2(nod*2,l,mid,lt,rt),query2(nod*2+1,mid+1,r,lt,rt));
}
int main(){
    cin >> n;
    for(int i = 1; i <= n ; i++){
        char ch;
        cin >> ch;
        if(ch == 'C')s[i]=-1;
        else s[i]=1;
    }
    for(int i = 1; i <= 4*n ; i++){
        st1[i] = -1e9;
        st2[i] = -1e9;
    }
    int sum = 0;
    for(int i = 1 ; i <= n; i++){
        sum += s[i];
        p1[i] = sum;
    }
    build1(1,1,n);
    sum = 0;
    for(int i = n ; i > 0; i--){
        sum += s[i];
        p2[i]=sum;
    }
    build2(1,1,n);
    cin >> q;
    int li, ri;
    for(int i = 1 ;i <= q ;i++){
        cin >> li >> ri;
        int v1 = query1(1,li,ri,1,n);
        int v2 = query2(1,li,ri,1,n);
        cout << max(0,max(v1 - p1[li-1],v2-p2[ri+1])) << endl;
    }
    return 0;
}

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -