제출 #1166866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166866		AzeTurk810	Election (BOI18_election)	C++20	0 / 100	3 ms	6720 KiB

election

// Telebe of adicto yani AzeTurk810
// Why i am not a teacher?  ?(idea from Ayxan007)
#include <bits/stdc++.h>

using namespace std;
using ll= int64_t;
using ull=unsigned int64_t;

# define mpll map<ll,ll>
# define umpll unordered_map<ll,ll>
# define vv vector<vector
# define vint vector<int>
# define vull vector<unsigned long long>
# define sint set<int>
# define vpri vector<pair<int,int>>
# define vll vector<long long>
# define vbl vector<bool>
# define vvint vector<vector<int>>
# define vvll vector<vector<long long>>

/* Other defines*/
# define qint queue<int>

//# define endl '\n'
# define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
# define range(a,b,c) for(int i=a;i<b;i+=c)
# define ranger(a,b,c) for(int r=a;r<b;r+=c)
# define arange(a,b,c) for(int i=a;i>b;i-=c)
# define bend(x) (x).begin(),(x).end()
# define pb push_back
# define sortv(v) sort((v).begin() , (v).end());
# define fori(x) for(int i=0;i<x;i++)
# define forj(y) for(int j=0;j<y;j++)
# define fori1(x) for(int i=1;i<=x;i++)
# define forj1(y) for(int j=1;j<=y;j++)
# define forn(x,c) for(int i=0;i<n;i+=c)
# define ff first
# define ss second
# define INFi 1e15
# define INFll 1e18
# define printfprs(v) for(int alma = 0;alma<(v).size();alma++){cout<<(v)[alma].ff<< ' '<<(v)[alma].ss<<endl;};
# define printfv(v) {for(int alol = 0 ; alol < (v).size() ; alol++){cout<<(v)[alol]<<' ';}cout << endl;}
# define ln '\n'
//# define T int_fast32_t
# define int ll
int n;

struct segmentTree
{
    int N , Null_val;
    vint t;
    segmentTree(int _n)
    {
        t.resize(_n * 4 , 0);
        N = _n;
    }
    void build(int v , int l , int r , vint &a)
    {
        if(l == r)
        {
            t[v] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build((v << 1) , l , mid , a);
        build((v << 1)|1 , mid + 1 , r , a);
        t[v] = t[(v << 1)] + t[(v << 1)|1];
    }
    void upd(int v , int l , int r  , int &val , int &pos)
    {
        if(l == r)
        {
            t[v] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if(mid >= pos)upd((v << 1) , l , mid , val,pos);
        else upd((v << 1)|1 , mid + 1 , r , val , pos);
        t[v] = t[(v << 1)] + t[(v << 1)|1];
    }
    int ask(int v , int l , int r ,int ql , int qr)
    {
        if(ql <= l && r <= qr)
        {
            return t[v];
        }
        if(ql > r || l > qr)return Null_val;
        int mid = (l + r) >> 1;
        return  ask((v << 1) , l , mid ,ql , qr) +
                ask((v << 1)|1 , mid + 1 , r ,ql , qr);
    }
};
const int maxN = 2e5 + 123;
segmentTree st(maxN);

class problem
{
public:
    bool solveyaxin = true;
    int n;
    string s;
    int q;
    vector<vector<pair<int,int>>> que;
    vector<int> res;
    void __brute_force__() {
    }
    void __init__() {
        que.clear();
        ;
    }
    void __read__() {
        cin >> n;
        cin >> s;
        cin >> q;
        que.resize(n);
        res.resize(n);
        // st = segmentTree(n);
        fori(q) {
        // cout << q << ' ' << n << ' ' <<i << endl;
            int l , r;
            cin >> l >> r;
            l--;r--;
            que[r].pb({l , i});
            // cout << l << ' ' << r << endl;
        };
    }
    void __ff__() {
    }
    void __proces__() {
        vector<int>v;
        for(int i = 0 ; i < n; i++) {
            if(s[i] == 'T') {
                v.pb(i);
            } else {
                int val = 1;
                st.upd(1, 0 , n - 1 , i , val);
                val = -1;
                if(!v.empty()){
                    st.upd(1 , 0 , n -1 , i , val);
                    v.pop_back();
                }
            }
            for(auto &[l , id] : que[i]) {
                int p = ll(st.ask(1  , 0 , n - 1 , l , i));
                int temp = 0;
                res[id] = v.size() - min(p , temp);
                // cout << v.size() << ' ' << res[id] << endl;
            }
        }
    }
    void __out__() {
        fori(q) cout << res[i] << ln;
    }
    void solve() {
        __init__();
        __read__();
        // cout << "sa" << endl;
        __ff__();
        if(!solveyaxin)__brute_force__();
        else __proces__();
        __out__();
    }
    
};

signed main()
{
    fastio;
    int t = 1;
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    //     freopen("log.txt", "w", stderr);
    // #endif
        // cout << 1 <<endl;
    // cin >> t;
    // cout << t << endl;

    while(t--) {
        problem pq;
        pq.solve();
    }
    return 0;
}

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