oj.uz

Submission #854876

# Submission time Handle Problem Language Result Execution time Memory
854876 2023-09-29T08:39:56 Z mychecksedad Election (BOI18_election) C++17
100 / 100
 980 ms 174612 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 2e6+100, M = 1e5+10, K = 22;

int n, q, go[N][K], dp[N][K][2], a[N];
string s, t;
vector<int> pref;
array<int, 3> T[N];
array<int, 3> combine(array<int, 3> x, array<int, 3> y){
  return {
    min(x[0], x[2] + y[0]),
    min(y[1], x[1] + y[2]),
    x[2] + y[2]
  };
}
 
void build(int l, int r, int k){
  if(l == r){
    T[k][0] = s[l - 1] == 'T' ? -1 : 0;
    T[k][1] = T[k][0];
    T[k][2] = s[l - 1] == 'T' ? -1 : 1;
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  T[k] = combine(T[k<<1], T[k<<1|1]);
}

array<int, 3> get(int l, int r, int ql, int qr, int k){
  if(ql > r || qr < l) return {0, 0, 0};
  if(ql <= l && r <= qr) return T[k];
  int m = l + r >> 1;
  auto x = get(l, m, ql, qr, k<<1);
  auto y = get(m+1, r, ql, qr, k<<1|1);
  return combine(x, y);
}

void solve(){
  cin >> n >> s;
  cin >> q;

  for(int i = 1; i <= n; ++i) a[i] = (s[i - 1] == 'T' ? -1 : 1);

  pref.resize(n + 1);
  
  pref[0] = 0;
  for(int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i];

  build(1, n, 1); 

  map<int, int> last;
  last[0] = n + 1;
  int sum = 0;
  for(int i = n; i >= 1; --i){
    sum += a[i];
    if(a[i] == -1){
      go[i][0] = i + 1;
      dp[i][0][0] = 1;
      dp[i][0][1] = 0;
    }
    else if(last[sum]){
      go[i][0] = last[sum];
      dp[i][0][1] = -get(1, n, i, go[i][0] - 1, 1)[1];
      dp[i][0][0] = 0;
    }else go[i][0] = n + 1, dp[i][0][1] = -get(1, n, i, n, 1)[1], dp[i][0][0] = 0;
    last[sum] = i;
  }
  go[n+1][0] = n+1;
  dp[n + 1][0][0] = 0;
  dp[n + 1][0][1] = 0;
  for(int j = 1; j < K; ++j){
    for(int i= 1; i <= n+1; ++i){
      go[i][j] = go[go[i][j - 1]][j - 1];
      dp[i][j][0] = dp[i][j - 1][0] + dp[go[i][j - 1]][j - 1][0];
      dp[i][j][1] = max(dp[i][j - 1][1], dp[go[i][j - 1]][j - 1][1]);
    }
  }

  for(int i = 0; i < q; ++i){
    int l, r; cin >> l >> r;
    pair<int, int> ans = {0, 0};
    for(int j = K - 1; j >= 0; --j){
      if(go[l][j] <= r){
        ans.first += dp[l][j][0];
        ans.second = max(dp[l][j][1], ans.second);
        l = go[l][j];
      }
    }
    int ss = pref[r] - pref[l - 1];
    ans.second = max(0, ans.second - ss);
    ans.second = max(ans.second, -get(1, n, l, r, 1)[1]);
    cout << ans.first + ans.second << '\n';
  }

}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> tt;
  while(tt--){
    solve();
    // en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

election.cpp: In function 'void build(int, int, int)':
election.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   int m = l+r>>1;
      |           ~^~
election.cpp: In function 'std::array<int, 3> get(int, int, int, int, int)':
election.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int m = l + r >> 1;
      |           ~~^~~
election.cpp: In function 'int main()':
election.cpp:108:15: warning: unused variable 'aa' [-Wunused-variable]
  108 |   int tt = 1, aa;
      |               ^~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 95 ms 27996 KB Output is correct
7 Correct 69 ms 27988 KB Output is correct
8 Correct 77 ms 28180 KB Output is correct
9 Correct 74 ms 27736 KB Output is correct
10 Correct 98 ms 28500 KB Output is correct
11 Correct 79 ms 28532 KB Output is correct
12 Correct 93 ms 28240 KB Output is correct
13 Correct 81 ms 29160 KB Output is correct
14 Correct 86 ms 28472 KB Output is correct
15 Correct 87 ms 29008 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 95 ms 27996 KB Output is correct
7 Correct 69 ms 27988 KB Output is correct
8 Correct 77 ms 28180 KB Output is correct
9 Correct 74 ms 27736 KB Output is correct
10 Correct 98 ms 28500 KB Output is correct
11 Correct 79 ms 28532 KB Output is correct
12 Correct 93 ms 28240 KB Output is correct
13 Correct 81 ms 29160 KB Output is correct
14 Correct 86 ms 28472 KB Output is correct
15 Correct 87 ms 29008 KB Output is correct
16 Correct 714 ms 162024 KB Output is correct
17 Correct 682 ms 162032 KB Output is correct
18 Correct 665 ms 162532 KB Output is correct
19 Correct 640 ms 161996 KB Output is correct
20 Correct 842 ms 166172 KB Output is correct
21 Correct 980 ms 168004 KB Output is correct
22 Correct 900 ms 167076 KB Output is correct
23 Correct 953 ms 170284 KB Output is correct
24 Correct 896 ms 168900 KB Output is correct
25 Correct 873 ms 174612 KB Output is correct