oj.uz

Submission #536345

# Submission time Handle Problem Language Result Execution time Memory
536345 2022-03-13T02:01:35 Z Evang Election (BOI18_election) C++17
100 / 100
 379 ms 26640 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


int n, q;
struct node{
    int sum, pre, suf, ans;
} tr[1'000'005];

node cmb(node x, node y){
    return node{
            x.sum+y.sum,
            max(x.sum+y.pre, x.pre),
            max(x.suf+y.sum, y.suf),
            max({x.pre+y.suf, x.sum+y.ans, x.ans+y.sum})
    };
}

void pull(int i){
    tr[i] = cmb(tr[2*i], tr[2*i+1]);
//    tr[i].sum = tr[2*i].sum + tr[2*i+1].sum;
//    tr[i].pre = max(tr[2*i].sum+tr[2*i+1].pre, tr[2*i].pre);
//    tr[i].suf = max(tr[2*i].suf+tr[2*i+1].sum, tr[2*i+1].suf);
//    tr[i].ans = max({tr[2*i].pre + tr[2*i+1].suf,
//            tr[2*i].sum+tr[2*i+1].ans, tr[2*i].ans+tr[2*i+1].ans});
}

int qry(int l, int r){
    l += n-1;
    r += n-1;
    node le{0, 0, 0, 0}, ri{0, 0, 0, 0};
    while(l<=r){
        if(l&1){
            le = cmb(le, tr[l]);
            ++l;
        }
        if(r&1^1){
            ri = cmb(tr[r], ri);
            --r;
        }
        l /= 2;
        r /= 2;
    }
    return cmb(le, ri).ans;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n;
    for(int i = n; i < 2*n; ++i){
        char c;
        cin >> c;
        tr[i].sum = c=='T'? 1:-1;
        tr[i].ans = tr[i].suf = tr[i].pre = max(0, tr[i].sum);
    }
    for(int i = n-1; i > 0; --i)
        pull(i);

    cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        cout << qry(l, r) << el;
    }
}

Compilation message

election.cpp: In function 'int qry(int, int)':
election.cpp:94:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   94 |         if(r&1^1){
      |            ~^~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 412 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 35 ms 3644 KB Output is correct
7 Correct 33 ms 3660 KB Output is correct
8 Correct 34 ms 3584 KB Output is correct
9 Correct 29 ms 3608 KB Output is correct
10 Correct 37 ms 3568 KB Output is correct
11 Correct 50 ms 3788 KB Output is correct
12 Correct 34 ms 3740 KB Output is correct
13 Correct 37 ms 3728 KB Output is correct
14 Correct 33 ms 3684 KB Output is correct
15 Correct 32 ms 3696 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 412 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 35 ms 3644 KB Output is correct
7 Correct 33 ms 3660 KB Output is correct
8 Correct 34 ms 3584 KB Output is correct
9 Correct 29 ms 3608 KB Output is correct
10 Correct 37 ms 3568 KB Output is correct
11 Correct 50 ms 3788 KB Output is correct
12 Correct 34 ms 3740 KB Output is correct
13 Correct 37 ms 3728 KB Output is correct
14 Correct 33 ms 3684 KB Output is correct
15 Correct 32 ms 3696 KB Output is correct
16 Correct 354 ms 25564 KB Output is correct
17 Correct 265 ms 25184 KB Output is correct
18 Correct 349 ms 25448 KB Output is correct
19 Correct 237 ms 24908 KB Output is correct
20 Correct 347 ms 24660 KB Output is correct
21 Correct 320 ms 26436 KB Output is correct
22 Correct 338 ms 26368 KB Output is correct
23 Correct 325 ms 26640 KB Output is correct
24 Correct 317 ms 26148 KB Output is correct
25 Correct 379 ms 25660 KB Output is correct