oj.uz

Submission #108019

# Submission time Handle Problem Language Result Execution time Memory
108019 2019-04-26T19:46:58 Z brcode Election (BOI18_election) C++14
100 / 100
 2017 ms 52068 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN =5e5+5;
struct node{
    int sum,suffsum;
    node(int sum = 0,int suffsum = 0){
        this->sum = sum;
        this->suffsum = suffsum;
    }
    node join(node &other){
        return node(sum+other.sum,min(other.suffsum,other.sum+suffsum));
    }
};
node a[4*MAXN + 5];
void update(int curr,int l,int r,int pos,int val){
    
    if(pos>r||pos<l){
        return;
    }
   // cout<<pos<<" "<<l<<" "<<r<<endl;
    if(l == r){
        a[curr].sum+=val;
        a[curr].suffsum+=val;
        return;
    }
    int mid = (l+r)/2;
    update(2*curr,l,mid,pos,val);
    update(2*curr+1,mid+1,r,pos,val);
    a[curr] = a[2*curr].join(a[2*curr+1]);
}
node query(int curr,int l, int r,int tl,int tr){
    if(tl>r||tr<l){
        node temp;
        temp.sum = 0;
        temp.suffsum = 0;
        return temp;
    }
    if(tl<=l && r<=tr){
        return a[curr];
    }
    int mid = (l+r)/2;
    node a = query(2*curr,l,mid,tl,tr);
    node b = query(2*curr+1,mid+1,r,tl,tr);
    return a.join(b);
}
int n,q;
int rem[MAXN];
int len;
int holdans[MAXN];
vector<pair<int,int>> queries[MAXN];
int main(){

    cin>>n;
    string s;
    cin>>s;
 
    cin>>q;
    
    s = '#' + s;
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        queries[l].push_back(make_pair(r,i));
    }
    for(int i=n;i>=1;i--){
        if(s[i] == 'T'){
            rem[len++] = i;
            
        }else{
            update(1,1,n,i,1);
           //cout<<query(1,1,n,i,n).suffsum<<endl;
            if(len){
                update(1,1,n,rem[len-1],-1);
                
                //cout<<rem[len-1]<<endl;
                len--;
            }
        }
        for(auto it:queries[i]){
            //cout<<len<<" "<<it.first<<endl;
            int l=0;
            int r = len-1;
            int ans = -1;
            while(l<=r){
                int mid = (l+r)/2;
               // cout<<rem[mid]<<endl;
                if(rem[mid]>it.first){
                    ans = mid;
                    //cout<<123<<" "<<mid<<" "<<rem[mid]<<" "<<it.first<<endl;
                    l=mid+1;
                }else{
                   
                    //ans = mid;
                    r=mid-1;
                }
            }
            //cout<<len<<" "<<len-ans-1<<endl;
            //cout<<len<<" "<<ans+1<<endl;
          //  cout<<-1*query(1,1,n,i,it.first).suffsum<<endl;
         //cout<<ans+1<<endl;
            holdans[it.second] = max(0,-1*query(1,1,n,i,it.first).suffsum) + len-ans-1;
            
        }
        
    }
    for(int i=1;i<=q;i++){
        cout<<holdans[i]<<endl;
    }
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 27768 KB Output is correct
2 Correct 29 ms 27896 KB Output is correct
3 Correct 32 ms 27768 KB Output is correct
4 Correct 28 ms 27748 KB Output is correct
5 Correct 33 ms 27768 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 27768 KB Output is correct
2 Correct 29 ms 27896 KB Output is correct
3 Correct 32 ms 27768 KB Output is correct
4 Correct 28 ms 27748 KB Output is correct
5 Correct 33 ms 27768 KB Output is correct
6 Correct 232 ms 29956 KB Output is correct
7 Correct 215 ms 29300 KB Output is correct
8 Correct 350 ms 29400 KB Output is correct
9 Correct 276 ms 29832 KB Output is correct
10 Correct 241 ms 29828 KB Output is correct
11 Correct 237 ms 30112 KB Output is correct
12 Correct 255 ms 30100 KB Output is correct
13 Correct 261 ms 30004 KB Output is correct
14 Correct 357 ms 29964 KB Output is correct
15 Correct 233 ms 29812 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 27768 KB Output is correct
2 Correct 29 ms 27896 KB Output is correct
3 Correct 32 ms 27768 KB Output is correct
4 Correct 28 ms 27748 KB Output is correct
5 Correct 33 ms 27768 KB Output is correct
6 Correct 232 ms 29956 KB Output is correct
7 Correct 215 ms 29300 KB Output is correct
8 Correct 350 ms 29400 KB Output is correct
9 Correct 276 ms 29832 KB Output is correct
10 Correct 241 ms 29828 KB Output is correct
11 Correct 237 ms 30112 KB Output is correct
12 Correct 255 ms 30100 KB Output is correct
13 Correct 261 ms 30004 KB Output is correct
14 Correct 357 ms 29964 KB Output is correct
15 Correct 233 ms 29812 KB Output is correct
16 Correct 2017 ms 49944 KB Output is correct
17 Correct 1656 ms 46612 KB Output is correct
18 Correct 1767 ms 47584 KB Output is correct
19 Correct 1525 ms 49340 KB Output is correct
20 Correct 1808 ms 49696 KB Output is correct
21 Correct 1845 ms 51856 KB Output is correct
22 Correct 1643 ms 51440 KB Output is correct
23 Correct 1708 ms 52068 KB Output is correct
24 Correct 1775 ms 51380 KB Output is correct
25 Correct 1818 ms 50832 KB Output is correct