oj.uz

Submission #546066

# Submission time Handle Problem Language Result Execution time Memory
546066 2022-04-06T08:23:02 Z Soul234 Election (BOI18_election) C++14
100 / 100
 577 ms 27984 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

const int MX = 1<<19;

struct Nod {
    int mncst, mxp, mxs, sum;
};

Nod comb(const Nod&lf, const Nod&rh) {
    return {
        max({lf.mxp + rh.mxs, lf.sum + rh.mncst, lf.mncst + rh.sum}),
        max(lf.mxp, lf.sum + rh.mxp),
        max(rh.mxs, rh.sum + lf.mxs),
        lf.sum + rh.sum,
    };
}

Nod st[MX<<1];
int N;
str s;

void build(int ind = 1, int L = 1, int R = N) {
    if(L == R) {
        if(s[L-1] == 'T') st[ind] = {1, 1, 1, 1};
        else st[ind] = {0,0,0,-1};
    }
    else {
        int mid = (L + R) >> 1;
        build(ind<<1, L, mid);
        build(ind<<1|1, mid+1, R);
        st[ind] = comb(st[ind<<1], st[ind<<1|1]);
    }
}

Nod query(int l, int r, int ind = 1, int L = 1, int R = N) {
    if(l > R || r < L) return {0,0,0,0};
    if(l <= L && R <= r) return st[ind];
    int mid = (L + R) >> 1;
    return comb(query(l,r,ind<<1, L, mid), query(l,r,ind<<1|1, mid+1, R));
}

void solve() {
    cin>>N>>s;
    build();
    int Q;
    cin>>Q;
    while(Q--) {
        int l, r;
        cin>>l>>r;
        cout << query(l,r).mncst << nl;
    }
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

election.cpp: In function 'void setIO(std::string)':
election.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 53 ms 5800 KB Output is correct
7 Correct 53 ms 5708 KB Output is correct
8 Correct 58 ms 5680 KB Output is correct
9 Correct 54 ms 5692 KB Output is correct
10 Correct 53 ms 5664 KB Output is correct
11 Correct 51 ms 5800 KB Output is correct
12 Correct 58 ms 5860 KB Output is correct
13 Correct 55 ms 5836 KB Output is correct
14 Correct 52 ms 5824 KB Output is correct
15 Correct 61 ms 5772 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 53 ms 5800 KB Output is correct
7 Correct 53 ms 5708 KB Output is correct
8 Correct 58 ms 5680 KB Output is correct
9 Correct 54 ms 5692 KB Output is correct
10 Correct 53 ms 5664 KB Output is correct
11 Correct 51 ms 5800 KB Output is correct
12 Correct 58 ms 5860 KB Output is correct
13 Correct 55 ms 5836 KB Output is correct
14 Correct 52 ms 5824 KB Output is correct
15 Correct 61 ms 5772 KB Output is correct
16 Correct 478 ms 26976 KB Output is correct
17 Correct 472 ms 26560 KB Output is correct
18 Correct 573 ms 26848 KB Output is correct
19 Correct 442 ms 26332 KB Output is correct
20 Correct 524 ms 26008 KB Output is correct
21 Correct 535 ms 27780 KB Output is correct
22 Correct 497 ms 27840 KB Output is correct
23 Correct 532 ms 27984 KB Output is correct
24 Correct 577 ms 27620 KB Output is correct
25 Correct 488 ms 27148 KB Output is correct