oj.uz

Submission #1031129

# Submission time Handle Problem Language Result Execution time Memory
1031129 2024-07-22T15:15:58 Z hasan2006 Election (BOI18_election) C++17
100 / 100
 792 ms 38068 KB 
#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 = 1; i <= n; i++){
        char ch;
        cin>>ch;
        a[i] = (ch == 'T' ? -1 : 1);
        b[i] = b[i - 1] + a[i];
        add(1 , 0 , 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 , 0 , n , k , n , 1) , d.push_back(k);
            else if(d.size())
                add(1 , 0 , n , d.back() , n , -1) , d.pop_back();
            k++;
        }
        ll L = 0 , R = d.size() , M;
        if(d.size()){
            while(L != R){
                M = (L + R) / 2;
                if(d[M] >= l)
                    R = M;
                else
                    L = M + 1;
            }
        }
        c[to.se.se] = (d.size() - L) + max(get(1 , 0 , n , l - 1 , l - 1) - get(1 , 0 , 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

election.cpp: In function 'void solve()':
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:46: warning: unused variable 'f' [-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
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 72 ms 8896 KB Output is correct
7 Correct 65 ms 8916 KB Output is correct
8 Correct 67 ms 8852 KB Output is correct
9 Correct 64 ms 8688 KB Output is correct
10 Correct 71 ms 8660 KB Output is correct
11 Correct 75 ms 8896 KB Output is correct
12 Correct 71 ms 8900 KB Output is correct
13 Correct 78 ms 8896 KB Output is correct
14 Correct 75 ms 8904 KB Output is correct
15 Correct 65 ms 8700 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 72 ms 8896 KB Output is correct
7 Correct 65 ms 8916 KB Output is correct
8 Correct 67 ms 8852 KB Output is correct
9 Correct 64 ms 8688 KB Output is correct
10 Correct 71 ms 8660 KB Output is correct
11 Correct 75 ms 8896 KB Output is correct
12 Correct 71 ms 8900 KB Output is correct
13 Correct 78 ms 8896 KB Output is correct
14 Correct 75 ms 8904 KB Output is correct
15 Correct 65 ms 8700 KB Output is correct
16 Correct 569 ms 36704 KB Output is correct
17 Correct 515 ms 36528 KB Output is correct
18 Correct 607 ms 36544 KB Output is correct
19 Correct 549 ms 36156 KB Output is correct
20 Correct 604 ms 35764 KB Output is correct
21 Correct 792 ms 37856 KB Output is correct
22 Correct 670 ms 37248 KB Output is correct
23 Correct 690 ms 38068 KB Output is correct
24 Correct 607 ms 37484 KB Output is correct
25 Correct 556 ms 36812 KB Output is correct