Submission #1031070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031070		hasan2006	Election (BOI18_election)	C++17	0 / 100	11 ms	16216 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 1e6 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , dp[N] , c[N] , d[N] , t[N * 3] , lz[N * 3];

void pushup(int i){
    t[i] = min(t[2 * i] , t[2 * i + 1]);
}

void pushlazy(int i){
    t[2 * i] += lz[i] , t[2 * i + 1] += lz[i];
    lz[2 * i + 1] += lz[i] , lz[2 * i] += lz[i];
    lz[i] = 0;
}

void add(int i , int l , int r , int tl , int tr , int x){
    int m = (l + r) / 2;
    if(l > tr || r < tl) return;
    if(l >= tl && r <= tr){
        t[i] += x , lz[i] += x;
    }else {
        pushlazy(i);
        add(2 * i , l , m , tl , tr , x);
        add(2 * i + 1 , m + 1 , r , tl , tr , x);
        pushup(i);
    }
}

ll get(int i , int l , int r , int tl , int tr){
    int m = (l + r) / 2;
    if(l > tr || r < tl) return 1e18;
    if(l >= tl && r <= tr){
        return t[i];
    }else {
        pushlazy(i);
        return min(get(2 * i , l , m , tl , tr) , get(2 * i + 1 , m + 1 , r , tl , tr));
    }
}

void solve()
{
    ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
    cin>>n;
    for(i = 0; i <= 2e6; i++)
        t[i] = 1e10;
    for(i = 1; i <= n; i++){
        char ch;
        cin>>ch;
        a[i] = (ch == 'T' ? -1 : 1);
        b[i] = b[i - 1] + a[i];
        add(1 , 1 , n, i , i, b[i]);
    }
    cin>>q;
    vector<pair<int,pair<int,int>>>v;
    for(i = 1; i <= q; i++)
        cin>>l>>r , v.pb({r , {l , i}});
    sort(all(v));
    deque<int>d;
    k = 1;
    for(auto to : v){
        l = to.se.fi , r = to.fi;
        while(k <= r){
            if(a[k] == -1)
                add(1 , 1 , n , k , n , 1) , d.push_back(k);
            else if(d.size())
                add(1 , 1 , n , d.back() , n , -1) , d.pop_back();
            k++;
        }
        c[to.se.se] = d.size() + max(b[l - 1] - get(1 , 1 , n , l , r) , 0ll);
    }
    for(i = 0; i <= 2e6; i++)
        t[i] = 1e10;
    reverse(a + 1 , a + n + 1);
    for(i = 1; i <= n; i++)
        b[i] = b[i - 1] + a[i] , add(1 , 1 , n , i , i , b[i]);
    for(i = 0; i < v.size(); i++){
        v[i].fi = n - v[i].fi + 1;
        v[i].se.fi = n - v[i].se.fi + 1;
        swap(v[i].fi , v[i].se.fi);
    }
    sort(all(v));
    d.clear();
    k = 1;
    for(auto to : v){
        l = to.se.fi , r = to.fi;
        while(k <= r){
            if(a[k] == -1)
                add(1 , 1 , n , k , n , 1) , d.push_back(k);
            else if(d.size())
                add(1 , 1 , n , d.back() , n , -1) , d.pop_back();
            k++;
        }
        f = d.size();
        c[to.se.se] = min(c[to.se.se] , f + max(b[l - 1] - get(1 , 1 , n , l , r) , 0ll));
    }
    for(i =1; i <= q;i ++)
        cout<<c[i]<<"\n";
}

int main(){
    TL;

    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    int t = 1;
    //cin>>t;
    while(t--)
     {
        solve();
     }
}
// Author : حسن

Compilation message (stderr)

election.cpp: In function 'void solve()':
election.cpp:94:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(i = 0; i < v.size(); i++){
      |                ~~^~~~~~~~~~
election.cpp:60:20: warning: unused variable 'j' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                    ^
election.cpp:60:30: warning: unused variable 'x' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                              ^
election.cpp:60:34: warning: unused variable 'y' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                  ^
election.cpp:60:38: warning: unused variable 's' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                      ^
election.cpp:60:54: warning: unused variable 'm' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                      ^
election.cpp:60:58: warning: unused variable 'mn' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                          ^~
election.cpp:60:69: warning: unused variable 'mx' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                                     ^~

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