제출 #280394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
280394		tc_abd	Election (BOI18_election)	C++14	0 / 100	6 ms	640 KiB

election

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define It it=se.begin();it!=se.end();it++
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define all(x) begin(x),end(x)
#define unmap unordered_map
#define pii pair<int,int>
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vi vector<int>
#define ld long double
#define ll long long
#define pb push_back
#define sh short int
#define mid (l+r)/2
#define S second
#define F first
#define sqr 708
using namespace std;
const int inf = 1e9+9;
const ll mod = 1e9+7;
const int shift = 1e5;
const ld pai=acos(-1);
int n,q;
int a[500009][9];
int tree[2000009][9];
string s;
void build(int node,int l,int r,int id){
    if(l == r) return void(tree[node][id]=a[l][id]);
    build(node*2,l,mid,id),build(node*2+1,mid+1,r,id);
    tree[node][id] = max(tree[node*2][id],tree[node*2+1][id]);
}
int query(int node,int l,int r,int s,int e,int id){
    if(s <= l && e >= r) return tree[node][id];
    if(s <= mid && e > mid){
        int x = query(node*2,l,mid,s,e,id);
        int y = query(node*2+1,mid+1,r,s,e,id);
        return max(x,y);
    }
    if(s <= mid) return query(node*2,l,mid,s,e,id);
    return query(node*2+1,mid+1,r,s,e,id);
}
int main(){
    fast,cin>>n>>s;
    s = '.' + s;
    for(int i=1;i<=n;i++){
        a[i][0] = a[i-1][0];
        a[i][0] += (s[i] == 'T');
        a[i][0] -= (s[i] == 'C');
    }
    for(int i=n;i>=1;i--){
        a[i][1] = a[i+1][1];
        a[i][1] += (s[i] == 'T');
        a[i][1] -= (s[i] == 'C');
    }
    build(1,0,n,0);
    build(1,0,n,1);
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        int x = query(1,0,n,l,r,0);
        int y = query(1,0,n,l,r,1);
        x -= a[l-1][0],y -= a[r+1][1];
        cout<<max(x,y)<<endl;
    }
}

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