oj.uz

Submission #259976

# Submission time Handle Problem Language Result Execution time Memory
259976 2020-08-08T21:25:43 Z fivefourthreeone Election (BOI18_election) C++17
100 / 100
 1105 ms 41664 KB 
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
gpu_hash_table<int, int> mp;
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>
 */
using ll = long long;
using ld = long double;
const ll MOD = 924844033;
const ll root = 62;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
//lets process in increasing order of right bound
const int mxN = 500001;
const int mxM = 524288;
vector<ttgl> query[mxN];
int sgmin[2*mxM];
int del[2*mxM];
int ans[mxN];
int n, q;
string S;
void push(int i) {
  del[2*i]+=del[i];
  del[2*i+1]+=del[i];
  del[i] = 0;
}
void resolve(int i) {
  sgmin[i] = min(sgmin[2*i] + del[2*i], sgmin[2*i+1] + del[2*i+1]); 
}
void upd(int l, int r, int ch, int i=1, int le = 0, int rr = n-1) {
  if(le>r||rr<l)return;
  if(le>=l&&rr<=r) {
    del[i]+=ch;
    return;
  }
  push(i);
  int mid = (le+rr)>>1;
  upd(l, r, ch, 2*i, le, mid);
  upd(l, r, ch, 2*i+1, mid+1, rr);
  resolve(i);
}
int qmin(int l, int r, int i=1, int le = 0, int rr = n-1) {
  if(l<0)return 0;
  if(le>r||rr<l) return INF;
  if(le>=l&&rr<=r) {
    return sgmin[i]+del[i];
  }
  push(i);
  resolve(i);
  int mid = (le+rr)>>1;
  return min(qmin(l, r, 2*i, le, mid), qmin(l, r, 2*i+1, mid+1, rr));
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>S>>q;
    int a, b;
    owo(i, 0, q) {
      cin>>a>>b;
      a--; b--;
      query[b].senpai({a, i});
    }
    vector<int> cnt;
    owo(i, 0, n) {
      if(S[i]=='T') {
        cnt.senpai(i);
      }else{
        if(cnt.size()){ 
          upd(cnt.back(), n-1, -1);
          cnt.pop_back();
        }
        upd(i, n-1, 1);
      }
      for(auto qq: query[i]) {
        int pos = lower_bound(cnt.begin(), cnt.end(), qq.first)-cnt.begin();
        ans[qq.second] = cnt.size()-pos + max(0, qmin(qq.first-1, qq.first-1)-qmin(qq.first, i));
      }
    }
    owo(i, 0, q) {
        cout<<ans[i]<<"\n";
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 14 ms 12160 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 14 ms 12160 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct
6 Correct 140 ms 16620 KB Output is correct
7 Correct 110 ms 16220 KB Output is correct
8 Correct 107 ms 16248 KB Output is correct
9 Correct 115 ms 16504 KB Output is correct
10 Correct 122 ms 16408 KB Output is correct
11 Correct 126 ms 16760 KB Output is correct
12 Correct 121 ms 16632 KB Output is correct
13 Correct 128 ms 16888 KB Output is correct
14 Correct 113 ms 16632 KB Output is correct
15 Correct 136 ms 16528 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 14 ms 12160 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct
6 Correct 140 ms 16620 KB Output is correct
7 Correct 110 ms 16220 KB Output is correct
8 Correct 107 ms 16248 KB Output is correct
9 Correct 115 ms 16504 KB Output is correct
10 Correct 122 ms 16408 KB Output is correct
11 Correct 126 ms 16760 KB Output is correct
12 Correct 121 ms 16632 KB Output is correct
13 Correct 128 ms 16888 KB Output is correct
14 Correct 113 ms 16632 KB Output is correct
15 Correct 136 ms 16528 KB Output is correct
16 Correct 1105 ms 39788 KB Output is correct
17 Correct 880 ms 36980 KB Output is correct
18 Correct 1096 ms 38024 KB Output is correct
19 Correct 936 ms 39508 KB Output is correct
20 Correct 1052 ms 38808 KB Output is correct
21 Correct 1047 ms 41220 KB Output is correct
22 Correct 1006 ms 40844 KB Output is correct
23 Correct 1036 ms 41664 KB Output is correct
24 Correct 1025 ms 40972 KB Output is correct
25 Correct 1041 ms 40040 KB Output is correct