Submission #145427

#	Time	Username	Problem	Language	Result	Execution time	Memory
145427		MKopchev	Election (BOI18_election)	C++14	100 / 100	914 ms	45524 KiB

election

#include <bits/stdc++.h>
using namespace std;
const int nmax=5e5+42;
int n,q;
char in[nmax],inp[nmax];
vector< pair<int/*right*/,int/*id*/> > seen[nmax];
int output[nmax];
vector<int> active_t;
struct info
{
    int sum;
    int least_suffix;
};
info tree[4*nmax];
info my_merge(info l,info r)
{
    info ret;
    ret.sum=l.sum+r.sum;
    ret.least_suffix=min(r.least_suffix,l.least_suffix+r.sum);
    return ret;
}
void update(int node,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tree[node].sum=val;
        tree[node].least_suffix=min(0,val);
        return;
    }
    int av=(l+r)/2;
    if(pos<=av)update(node*2,l,av,pos,val);
    else update(node*2+1,av+1,r,pos,val);
    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
info query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree[node];
    info ret;ret.least_suffix=0;ret.sum=0;
    int av=(l+r)/2;

    if(av<rq)ret=my_merge(query(node*2+1,av+1,r,max(av+1,lq),rq),ret);
    if(lq<=av)ret=my_merge(query(node*2,l,av,lq,min(av,rq)),ret);

    return ret;
}
int main()
{
    scanf("%i",&n);
    scanf("%s",&in);

    for(int i=1;i<=n;i++)
        inp[i]=in[i-1];

    for(int i=1;i<=n;i++)
        if(inp[i]=='T')update(1,1,n,i,-1);
        else update(1,1,n,i,1);

    scanf("%i",&q);

    int l,r;
    for(int i=1;i<=q;i++)
    {
        scanf("%i%i",&l,&r);
        seen[l].push_back({r,i});
    }

    for(int i=n;i>=1;i--)
    {
        if(inp[i]=='T')
        {
            active_t.push_back(i);
            update(1,1,n,active_t.back(),0);
        }
        else
        {
            if(active_t.size())
            {
                update(1,1,n,active_t.back(),-1);
                active_t.pop_back();
            }
        }

        for(auto k:seen[i])
        {
            int ok=-1,not_ok=active_t.size();
            while(not_ok-ok>1)
            {
                int av=(ok+not_ok)/2;
                if(active_t[av]>k.first)ok=av;
                else not_ok=av;
            }

            output[k.second]=active_t.size()-ok-1;

            output[k.second]-=query(1,1,n,i,k.first).least_suffix;
        }

    }

    for(int i=1;i<=q;i++)
        printf("%i\n",output[i]);
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:49:19: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[500042]' [-Wformat=]
     scanf("%s",&in);
                ~~~^
election.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
election.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",&in);
     ~~~~~^~~~~~~~~~
election.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
election.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&l,&r);
         ~~~~~^~~~~~~~~~~~~~

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