oj.uz

답안 #151856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
151856 2019-09-05T06:36:17 Z Knps4422 Election (BOI18_election) C++14
0 / 100
 9 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];
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]);
    }
}
void update1(int nod , int l , int r , int pos , int val){
    if(l > r)return ;
    if(pos <= r && pos >= l){
            st1[nod] = max(st1[nod],val);
            int mid = (l+r)/2;
            update1(2*nod  ,l    ,mid,pos,val);
            update1(2*nod+1,mid+1,r  ,pos,val);
    }
    return ;
}
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));
}
void update2(int nod , int l , int r , int pos , int val){
    if(l > r)return ;
    if(pos <= r && pos >= l){
            st2[nod] = max(st2[nod],val);
    }else{
        return ;
    }
    int mid = (l+r)/2;
    update2(2*nod,l,mid,pos,val);
    update2(2*nod+1,mid+1,r,pos,val);
}
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 l, r;
    for(int i = 1 ;i <= n ;i++){
        cin >> l >> r;
        int v1 = query1(1,l,r,1,n);
        int v2 = query2(1,l,r,1,n);
        cout << max(0,max(v1 - p1[l-1],v2-p2[r+1])) << '\n';
    }
    return 0;
}

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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