Submission #86835

#	Time	Username	Problem	Language	Result	Execution time	Memory
86835		Mercenary	Election (BOI18_election)	C++11	100 / 100	847 ms	121624 KiB

election

#include<bits/stdc++.h>

using namespace std;
#define brokenheart "TEST"
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 5e5 + 5;

int n , q;
string s;

namespace IT
{
    const int cant = 1e9;
    struct TNode
    {
        int dep , suf;
        TNode(int _x , int _y) : dep(_x) , suf (_y) {};
        TNode (char x){dep = suf = (x == 'C' ? 1 : -1);}
        TNode(){};
        TNode operator + (const TNode & other) const &
        {
            if(suf == cant)return other;
            if(other.suf == cant)return (*this);
            TNode res;
            res.dep = dep + other.dep;
            res.suf = min(other.suf,other.dep+suf);
            return res;
        }
    }a[maxn * 4];

    TNode query(int x , int l , int r , int L , int R)
    {
        if(l > R || L > r)return TNode(cant,cant);
        if(L <= l && r <= R)return a[x];
        int mid = l + r >> 1;
        return query(x * 2 , l , mid , L , R) + query(x * 2 + 1 , mid + 1 , r , L , R);
    }

    TNode query(int l , int h){return query(1,1,n,l,h);};

    void update(int x , int l , int r , int pos , int val)
    {
        if(l == r)
        {
            a[x] = TNode(val,val);
            return;
        }
        int mid = l + r >> 1;
        if(mid >= pos)update(x * 2 , l , mid , pos , val);
        else update(x * 2 + 1 , mid + 1 , r , pos , val);
        a[x] = a[x * 2] + a[x * 2 + 1];
    }

    void update(int pos , int val){update(1,1,n,pos,val);}

    void build(int x , int l , int h)
    {
        if(l == h)
        {
            a[x] = TNode(s[l]);
            return;
        }
        int mid = l + h >> 1;
        build(x * 2 , l , mid);
        build(x * 2 + 1 , mid + 1 , h);
        a[x] = a[x * 2] + a[x * 2 + 1];
    }

    void build()
    {
        s = " " + s;
        build(1 , 1 , n);
    }
}

struct TQuery
{
    int h , id;
};

int res[maxn];
vector<TQuery> Vq[maxn];

vector<int> del;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if(fopen(brokenheart".INP","r"))
        freopen(brokenheart".INP", "r",stdin) ,
        freopen(brokenheart".OUT", "w",stdout);
    cin >> n >> s;
    IT::build();
    cin >> q;
    for(int i = 1 ; i <= q ; ++i)
    {
        int l , h;cin >> l >> h;
        Vq[l].pb({h , i});
    }
    for(int i = n ; i >= 1 ; --i)
    {
        if(s[i] == 'T')
        {
            IT::update(i,0);
            del.push_back(i);
        }
        else
        {
            if(!del.empty())
            {
                IT::update(del.back(),-1);
                del.pop_back();
            }
        }
        for(auto q : Vq[i])
        {
            res[q.id] = (upper_bound(del.rbegin(),del.rend(),q.h) - del.rbegin())
                - min(IT::query(i,q.h).suf,0);
//            cout << q.id << " " << IT::query(i,q.h).suf << '\n';
        }
    }
    for(int i = 1 ; i <= q ; ++i)cout << res[i] << '\n';
}

Compilation message (stderr)

election.cpp: In function 'IT::TNode IT::query(int, int, int, int, int)':
election.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
election.cpp: In function 'void IT::update(int, int, int, int, int)':
election.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
election.cpp: In function 'void IT::build(int, int, int)':
election.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + h >> 1;
                   ~~^~~
election.cpp: In function 'int main()':
election.cpp:93:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(brokenheart".INP", "r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(brokenheart".OUT", "w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
election.cpp:93:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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