Submission #96563

#TimeUsernameProblemLanguageResultExecution timeMemory
96563josiftepeElection (BOI18_election)C++14
100 / 100
1824 ms58528 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 5e5 + 10; int n; string s; bool visited[maxn]; int arr[maxn]; int solve(int S, int E){ int balance = 0; int ret = 0; memset(visited, false, sizeof visited); for(int i = S; i <= E; i ++){ if(s[i] == 'C'){ balance ++; arr[i] = 1; } else{ balance --; arr[i] = -1; } if(balance < 0){ balance = 0; visited[i] = true; // arr[i] = 0; ret ++; } } int suff_sum = 0; int mnn = (1 << 30); for(int i = S; i <= S; i ++){ suff_sum += arr[i]; // mnn = min(mnn, min(0, -suff_sum)); } balance = 0; for(int i = E; i >= S; i --){ if(s[i] == 'C'){ balance ++; } else if(!visited[i] and s[i] == 'T'){ balance --; } // cout << balance << " " ; mnn = min(mnn, min(0, -balance)); if(balance < 0){ balance = 0; // ret ++; } } return ret + abs(mnn); } struct elem{ int L, R, sum, min_suf; elem(){ L = R = sum = min_suf = 0; } }; elem mymerge(elem A, elem B){ elem ret; ret.R = max(A.R, B.R - A.min_suf); ret.sum = max(B.sum, A.sum - B.min_suf); ret.min_suf = A.min_suf + B.min_suf; ret.L = max(max(A.L - B.min_suf, B.L - A.min_suf), A.R + B.sum); return ret; } class node{ public: elem val; int lb, rb; node *left, *right; node(int levo, int desno){ lb = levo; rb = desno; if(levo == desno){ if(s[levo] == 'T'){ val.L = val.R = val.sum = 1; val.min_suf = -1; } else{ val.L = val.R = val.sum = 0; val.min_suf = 1; } } else{ int mid = (levo + desno) >> 1; left = new node(levo, mid); right = new node(mid + 1, desno); val = mymerge(left -> val, right -> val); } } elem query(int i, int j){ if(i <= lb and rb <= j){ return val; } /// i j l r i j if(j < lb or rb < i){ return elem(); } return mymerge(left -> query(i, j), right -> query(i, j)); } }; int main() { ios_base::sync_with_stdio(false); //ifstream cin("in.txt.txt"); cin >> n >> s; int q; cin >> q; node *root = new node(0, n - 1); for(int i = 0; i < q; i ++){ int a, b; cin >> a >> b; a --; b --; cout << root -> query(a, b).L << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...