Submission #1264648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264648		yoshi_33550336	Election (BOI18_election)	C++20	100 / 100	240 ms	20252 KiB

election

#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem "election"
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
struct Node
{
    int RS;
    int Sum = 0;
    Node()
    {
        RS = 1e9;
    }
    Node(int x)
    {
        RS = Sum = x;
    }
};
Node merge(const Node &L, const Node &R)
{
    if (L.RS == 1e9)
        return R;
    if (R.RS == 1e9)
        return L;
    Node res;
    res.RS = min(R.RS, R.Sum + L.RS);
    res.Sum = L.Sum + R.Sum;
    return res;
}
struct ST
{
    vector<Node> t;
    int n = 0;
    ST()
    {
    }
    ST(int n) : n(n)
    {
        t.resize(2 * n);
        fill(t.begin() + n, t.end(), Node(0));
        for (int i = n - 1; i > 0; i--)
            t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    void modify(int p, int value)
    {
        for (t[p += n] = value; p > 1; p >>= 1)
            t[p >> 1] = merge(t[p - (p & 1)], t[p + (~p & 1)]);
    }
    Node query(int l, int r)
    {
        Node resl, resr;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                resl = merge(resl, t[l++]);
            if (r & 1)
                resr = merge(t[--r], resr);
        }
        return merge(resl, resr);
    }
};
ST Stx(500000);
struct Tp3
{
    int x, y, z;
};
void Yoshi()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int q;
    cin >> q;
    vector<Tp3> qus(q);
    for (auto &i : qus)
        cin >> i.x >> i.y, i.x--, i.y--, i.z = &i - &qus[0];
    sort(qus.begin(), qus.end(), [](auto &a, auto &b)
         { return a.x > b.x; });
    vector<int> Tp, qres(q);
    int ptr = n - 1;
    for (auto &[l, r, id] : qus)
    {
        while (ptr >= l)
        {
            if (s[ptr] == 'T')
                Tp.push_back(ptr);
            else
            {
                Stx.modify(ptr, 1);
                if (Tp.size())
                {
                    Stx.modify(Tp.back(), -1);
                    Tp.pop_back();
                }
            }
            ptr--;
        }
        qres[id] = upper_bound(Tp.rbegin(), Tp.rend(), r) - Tp.rbegin() - min(0, Stx.query(l, r + 1).RS);
    }
    for (auto &i : qres)
        cout << i << endl;
}
signed main()
{
#ifndef yoshi_likes_e4
    ios::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    cin >> t;
#endif
    while (t--)
        Yoshi();
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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