oj.uz

Submission #145427

# Submission time Handle Problem Language Result Execution time Memory
145427 2019-08-19T20:21:13 Z MKopchev Election (BOI18_election) C++14
100 / 100
 914 ms 45524 KB 
#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12284 KB Output is correct
2 Correct 15 ms 12152 KB Output is correct
3 Correct 13 ms 12152 KB Output is correct
4 Correct 15 ms 12280 KB Output is correct
5 Correct 14 ms 12280 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12284 KB Output is correct
2 Correct 15 ms 12152 KB Output is correct
3 Correct 13 ms 12152 KB Output is correct
4 Correct 15 ms 12280 KB Output is correct
5 Correct 14 ms 12280 KB Output is correct
6 Correct 103 ms 17184 KB Output is correct
7 Correct 90 ms 16696 KB Output is correct
8 Correct 101 ms 16892 KB Output is correct
9 Correct 104 ms 17144 KB Output is correct
10 Correct 98 ms 17104 KB Output is correct
11 Correct 106 ms 17528 KB Output is correct
12 Correct 103 ms 17328 KB Output is correct
13 Correct 107 ms 17528 KB Output is correct
14 Correct 100 ms 17432 KB Output is correct
15 Correct 97 ms 17272 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12284 KB Output is correct
2 Correct 15 ms 12152 KB Output is correct
3 Correct 13 ms 12152 KB Output is correct
4 Correct 15 ms 12280 KB Output is correct
5 Correct 14 ms 12280 KB Output is correct
6 Correct 103 ms 17184 KB Output is correct
7 Correct 90 ms 16696 KB Output is correct
8 Correct 101 ms 16892 KB Output is correct
9 Correct 104 ms 17144 KB Output is correct
10 Correct 98 ms 17104 KB Output is correct
11 Correct 106 ms 17528 KB Output is correct
12 Correct 103 ms 17328 KB Output is correct
13 Correct 107 ms 17528 KB Output is correct
14 Correct 100 ms 17432 KB Output is correct
15 Correct 97 ms 17272 KB Output is correct
16 Correct 843 ms 43504 KB Output is correct
17 Correct 677 ms 39544 KB Output is correct
18 Correct 753 ms 40512 KB Output is correct
19 Correct 721 ms 42292 KB Output is correct
20 Correct 845 ms 42548 KB Output is correct
21 Correct 914 ms 44844 KB Output is correct
22 Correct 863 ms 44436 KB Output is correct
23 Correct 908 ms 45524 KB Output is correct
24 Correct 849 ms 44516 KB Output is correct
25 Correct 802 ms 43840 KB Output is correct