oj.uz

Submission #854875

# Submission time Handle Problem Language Result Execution time Memory
854875 2023-09-29T08:39:27 Z mychecksedad Election (BOI18_election) C++17
82 / 100
 110 ms 35816 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 = 1e6+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 3 ms 6492 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 3 ms 6620 KB Output is correct
5 Correct 3 ms 6708 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 3 ms 6492 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 3 ms 6620 KB Output is correct
5 Correct 3 ms 6708 KB Output is correct
6 Correct 74 ms 31016 KB Output is correct
7 Correct 71 ms 30832 KB Output is correct
8 Correct 81 ms 30888 KB Output is correct
9 Correct 75 ms 30944 KB Output is correct
10 Correct 81 ms 31316 KB Output is correct
11 Correct 81 ms 31428 KB Output is correct
12 Correct 86 ms 31312 KB Output is correct
13 Correct 82 ms 32088 KB Output is correct
14 Correct 84 ms 31404 KB Output is correct
15 Correct 110 ms 32164 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 3 ms 6620 KB Output is correct
5 Correct 3 ms 6708 KB Output is correct
6 Correct 74 ms 31016 KB Output is correct
7 Correct 71 ms 30832 KB Output is correct
8 Correct 81 ms 30888 KB Output is correct
9 Correct 75 ms 30944 KB Output is correct
10 Correct 81 ms 31316 KB Output is correct
11 Correct 81 ms 31428 KB Output is correct
12 Correct 86 ms 31312 KB Output is correct
13 Correct 82 ms 32088 KB Output is correct
14 Correct 84 ms 31404 KB Output is correct
15 Correct 110 ms 32164 KB Output is correct
16 Runtime error 28 ms 35816 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -