oj.uz

Submission #888590

# Submission time Handle Problem Language Result Execution time Memory
888590 2023-12-17T23:42:12 Z yfrank792 Election (BOI18_election) C++14
82 / 100
 141 ms 36180 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef queue<int> qi;
typedef set<int> si;

typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<int,vi,greater<int> > pqi_g;
typedef priority_queue<ll,vll,greater<ll> > pql_g;

#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
#define FOR(i,a,b) for (int i=a; i<=b; i++)
#define _FOR(i,a,b) for (int i=a; i>=b; i--)
#define F0R(i,a,b,x) for (int i=a; i<=b; i+=x)
#define FOR_(x,v) for (auto x : v)
#define F0R_(x,v) for (auto &x : v)

const int INF = 0x3f3f3f3f;
const int maxn = 5e5+5;
const ll MOD = 1e9+7;

//? link: https://oj.uz/problem/view/BOI18_election

//? sol: 

int n, q;

class segtree {
    struct node {ll mx_pre,mx_suf,sum,ans;} d[maxn];
    private:
        ll inline ls(ll x) {return x<<1;}
        ll inline rs(ll x) {return x<<1|1;}
        node inline op(node &l,node &r) {
            return {
                max(l.mx_pre, l.sum+r.mx_pre),
                max(r.mx_suf, r.sum+l.mx_suf),
                l.sum + r.sum,
                max(max(l.ans+r.sum, l.sum+r.ans), l.mx_pre+r.mx_suf)
            };
        }
    public:
        ll a[maxn];     // 1 if T, -1 if C
        void init(ll s=1,ll t=n,ll p=1) {
            if (s==t) {
                ll tmp = (ll)a[s];
                d[p] = {max(tmp,0ll),max(tmp,0ll),tmp,max(tmp,0ll)};    // mx_pre, mx_suf, sum, ans
                // note: mx_pre and mx_suf can be 0 when it's C (taking prefix/suffix sum of no elements)
                return;
            }
            ll mid = s + ((t-s)>>1);
            init(s, mid, ls(p));
            init(mid+1, t, rs(p));
            d[p] = op(d[ls(p)], d[rs(p)]);
        }
        node query(ll l,ll r,ll s=1,ll t=n,ll p=1) {      // query(l,r)
            if (l<=s && t<=r) return d[p];
            ll mid = s + ((t-s)>>1);
            node lch, rch;
            if (l<=mid) lch=query(l,r,s,mid,ls(p));
            else lch={0,0,0,0};
            if (r>mid) rch=query(l,r,mid+1,t,rs(p));
            else rch={0,0,0,0};
            return op(lch,rch);
        }
} st;

int a[maxn];

int main()
{
    // faster cin/cout
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // freopen("c.in","r",stdin);

    cin >> n;
    FOR(i,1,n) {
        char c; cin>>c;
        st.a[i] = (c=='C'? -1:1);
    }
    st.init();

    cin >> q;
    FOR(_,1,q) {
        int l,r; cin>>l>>r;
        cout << st.query(l,r).ans << endl;
    }

    return 0;   
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 4 ms 4444 KB Output is correct
3 Correct 4 ms 4444 KB Output is correct
4 Correct 4 ms 4584 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 113 ms 13892 KB Output is correct
7 Correct 112 ms 13848 KB Output is correct
8 Correct 112 ms 13728 KB Output is correct
9 Correct 111 ms 13652 KB Output is correct
10 Correct 113 ms 13664 KB Output is correct
11 Correct 114 ms 13908 KB Output is correct
12 Correct 141 ms 13984 KB Output is correct
13 Correct 120 ms 13972 KB Output is correct
14 Correct 118 ms 13948 KB Output is correct
15 Correct 119 ms 13924 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 4 ms 4444 KB Output is correct
3 Correct 4 ms 4444 KB Output is correct
4 Correct 4 ms 4584 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 113 ms 13892 KB Output is correct
7 Correct 112 ms 13848 KB Output is correct
8 Correct 112 ms 13728 KB Output is correct
9 Correct 111 ms 13652 KB Output is correct
10 Correct 113 ms 13664 KB Output is correct
11 Correct 114 ms 13908 KB Output is correct
12 Correct 141 ms 13984 KB Output is correct
13 Correct 120 ms 13972 KB Output is correct
14 Correct 118 ms 13948 KB Output is correct
15 Correct 119 ms 13924 KB Output is correct
16 Runtime error 21 ms 36180 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -