oj.uz

Submission #173595

# Submission time Handle Problem Language Result Execution time Memory
173595 2020-01-04T16:54:47 Z nikolapesic2802 Election (BOI18_election) C++14
82 / 100
 3000 ms 11560 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}

const int N=5e5+5,L=707;
string s;
int uzimam[L][L+1],sum[L][L+1],mn[L][L+1],delta[L][L+1];
int cnt[L];
void init(){
    for(int o=0;o<L;o++){
        int l=o*L,r=(o+1)*L-1;
        //printf("%i-%i!\n",l,r);
        for(int i=l;i<=r;i++)
            if(s[i]=='T')
                cnt[o]++;
        int m=0,d=0;
        for(int i=r;i>=l;i--){
            if(s[i]=='T')
                d--;
            else
                d++;
            m=min(m,d);
        }
        for(int i=cnt[o];i<=L;i++){
            sum[o][i]=i+L-2*cnt[o];
            mn[o][i]=m;
            delta[o][i]=d;
        }
        for(int i=0;i<cnt[o];i++){
            vector<bool> uzet(L);
            int tr=i,cntt=0;
            for(int j=l;j<=r;j++){
                if(s[j]=='T')
                    tr--;
                else
                    tr++;
                if(tr<0)
                    uzet[j-l]=1,tr++,cntt++;
            }
            uzimam[o][i]=cntt;
            sum[o][i]=tr;
            m=0,d=0;
            for(int j=r;j>=l;j--){
                if(s[j]=='T'){
                    if(!uzet[j-l])
                        d--;
                }
                else
                    d++;
                m=min(m,d);
            }
            mn[o][i]=m;
            delta[o][i]=d;
        }
        /*for(int i=0;i<=L;i++)
            printf("%i %i: uzimam: %i sum: %i mn: %i delta: %i\n",o,i,uzimam[o][i],sum[o][i],mn[o][i],delta[o][i]);*/
    }
}
int calc(int l,int r){
    int le=l/L,ri=r/L;
    //printf("%i %i  %i %i\n",l,r,le,ri);
    if(le==ri){
        vector<bool> uzet(L);
        int tr=0,ans=0;
        for(int i=l;i<=r;i++){
            if(s[i]=='T')
                tr--;
            else
                tr++;
            if(tr<0)
                ans++,tr++,uzet[i-l]=1;
        }
        tr=0;
        for(int i=r;i>=l;i--){
            if(s[i]=='T'){
                if(!uzet[i-l])
                    tr--;
            }
            else
                tr++;
            if(tr<0)
                tr++,ans++;
        }
        return ans;
    }
    vector<bool> uzetL(L),uzetR(L);
    int tr=0,ans=0;
    for(int i=l;i<(le+1)*L;i++){
        if(s[i]=='T')
            tr--;
        else
            tr++;
        if(tr<0)
            ans++,tr++,uzetL[i-l]=1;
    }
    vector<int> vals(L);
    for(int i=le+1;i<ri;i++){
        vals[i]=min(L,tr);
        if(tr>=L){
            tr+=L-2*cnt[i];
            continue;
        }
        ans+=uzimam[i][tr];
        tr=sum[i][tr];
    }
    for(int i=ri*L;i<=r;i++){
        if(s[i]=='T')
            tr--;
        else
            tr++;
        if(tr<0)
            ans++,tr++,uzetR[r-i]=1;
    }
    tr=0;
    for(int i=r;i>=ri*L;i--){
        if(s[i]=='T'){
            if(!uzetR[r-i])
                tr--;
        }
        else
            tr++;
        if(tr<0)
            ans++,tr++;
    }
    for(int i=ri-1;i>le;i--){
        int d=-mn[i][vals[i]]-tr;
        if(d>0){
            ans+=d;
            tr+=d;
        }
        tr+=delta[i][vals[i]];
    }
    for(int i=(le+1)*L-1;i>=l;i--){
        if(s[i]=='T'){
            if(!uzetL[i-l])
                tr--;
        }
        else
            tr++;
        if(tr<0)
            ans++,tr++;
    }
    return ans;
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int n,q,l,r;
	cin >> n >> s >> q;
	while(s.size()!=N)
        s+='C';
    init();
    while(q--){
        cin >> l >> r;
        cout << calc(l-1,r-1) << endl;
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6832 KB Output is correct
2 Correct 33 ms 6828 KB Output is correct
3 Correct 32 ms 6828 KB Output is correct
4 Correct 33 ms 6828 KB Output is correct
5 Correct 26 ms 6956 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6832 KB Output is correct
2 Correct 33 ms 6828 KB Output is correct
3 Correct 32 ms 6828 KB Output is correct
4 Correct 33 ms 6828 KB Output is correct
5 Correct 26 ms 6956 KB Output is correct
6 Correct 1169 ms 8476 KB Output is correct
7 Correct 1185 ms 8340 KB Output is correct
8 Correct 1195 ms 8444 KB Output is correct
9 Correct 819 ms 8516 KB Output is correct
10 Correct 1137 ms 8212 KB Output is correct
11 Correct 1206 ms 8708 KB Output is correct
12 Correct 594 ms 8372 KB Output is correct
13 Correct 650 ms 8496 KB Output is correct
14 Correct 582 ms 8440 KB Output is correct
15 Correct 526 ms 8432 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6832 KB Output is correct
2 Correct 33 ms 6828 KB Output is correct
3 Correct 32 ms 6828 KB Output is correct
4 Correct 33 ms 6828 KB Output is correct
5 Correct 26 ms 6956 KB Output is correct
6 Correct 1169 ms 8476 KB Output is correct
7 Correct 1185 ms 8340 KB Output is correct
8 Correct 1195 ms 8444 KB Output is correct
9 Correct 819 ms 8516 KB Output is correct
10 Correct 1137 ms 8212 KB Output is correct
11 Correct 1206 ms 8708 KB Output is correct
12 Correct 594 ms 8372 KB Output is correct
13 Correct 650 ms 8496 KB Output is correct
14 Correct 582 ms 8440 KB Output is correct
15 Correct 526 ms 8432 KB Output is correct
16 Execution timed out 3040 ms 11560 KB Time limit exceeded
17 Halted 0 ms 0 KB -