oj.uz

Submission #108018

# Submission time Handle Problem Language Result Execution time Memory
108018 2019-04-26T19:46:25 Z brcode Election (BOI18_election) C++14
82 / 100
 276 ms 13388 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN =1e5+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 12 ms 5888 KB Output is correct
2 Correct 15 ms 5932 KB Output is correct
3 Correct 12 ms 5888 KB Output is correct
4 Correct 12 ms 5888 KB Output is correct
5 Correct 12 ms 5888 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5888 KB Output is correct
2 Correct 15 ms 5932 KB Output is correct
3 Correct 12 ms 5888 KB Output is correct
4 Correct 12 ms 5888 KB Output is correct
5 Correct 12 ms 5888 KB Output is correct
6 Correct 246 ms 8820 KB Output is correct
7 Correct 206 ms 8444 KB Output is correct
8 Correct 250 ms 8528 KB Output is correct
9 Correct 217 ms 8820 KB Output is correct
10 Correct 276 ms 9076 KB Output is correct
11 Correct 238 ms 8992 KB Output is correct
12 Correct 230 ms 8952 KB Output is correct
13 Correct 229 ms 9076 KB Output is correct
14 Correct 268 ms 8948 KB Output is correct
15 Correct 217 ms 8820 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5888 KB Output is correct
2 Correct 15 ms 5932 KB Output is correct
3 Correct 12 ms 5888 KB Output is correct
4 Correct 12 ms 5888 KB Output is correct
5 Correct 12 ms 5888 KB Output is correct
6 Correct 246 ms 8820 KB Output is correct
7 Correct 206 ms 8444 KB Output is correct
8 Correct 250 ms 8528 KB Output is correct
9 Correct 217 ms 8820 KB Output is correct
10 Correct 276 ms 9076 KB Output is correct
11 Correct 238 ms 8992 KB Output is correct
12 Correct 230 ms 8952 KB Output is correct
13 Correct 229 ms 9076 KB Output is correct
14 Correct 268 ms 8948 KB Output is correct
15 Correct 217 ms 8820 KB Output is correct
16 Runtime error 28 ms 13388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -