oj.uz

Submission #486942

# Submission time Handle Problem Language Result Execution time Memory
486942 2021-11-13T13:44:01 Z Victor Election (BOI18_election) C++17
0 / 100
 1 ms 844 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

string str;

struct Node {
    Node *l,*r;
    int lo,hi,sum,best,pref,suf;
    Node(int L,int R) : lo(L), hi(R) {
        if(hi-lo==1){
            sum=str[lo]=='C'?-1:1;
            best=pref=suf=max(sum,0);

        } else {
            int mid=(lo+hi)/2;
            l=new Node(lo,mid);
            r=new Node(mid,hi);

            best=max(max(l->best+r->sum,l->sum+r->best),l->pref+r->suf);
            sum=l->sum+r->sum;
            pref=max(l->pref,l->sum+r->pref);
            suf=max(r->suf,r->sum+l->suf);
        }
    }

    pair<ii,ii>query(int L,int R){
        if(hi<=L||R<=lo)return {{0,0},{0,0}};
        if(L<=lo&&hi<=R)return {{sum,best},{pref,suf}};

        int lsum,lbest,lpref,lsuf;
        auto val=l->query(L,R);
        tie(lsum,lbest)=val.first;
        tie(lpref,lsuf)=val.second;

        int rsum,rbest,rpref,rsuf;
        val=r->query(L,R);
        tie(rsum,rbest)=val.first;
        tie(rpref,rsuf)=val.second;

        int cur_sum=lsum+rsum;
        int cur_best=max(max(lbest+rsum,lsum+rbest),lpref+rsuf);
        int cur_pref=max(l->pref,l->sum+r->pref);
        int cur_suf=max(r->suf,r->sum+l->suf);

        return {{cur_sum,cur_best},{cur_pref,cur_suf}};
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n,q;
    cin>>n>>str>>q;

    Node segtree(0,n);

    while(q--){
        int lo,hi;
        cin>>lo>>hi;

		auto val=segtree.query(lo-1,hi);
		int best=val.first.second,pref,suf;
		tie(pref,suf)=val.second;

		assert(best>=max(pref,suf));
        cout<<best<<endl;
    }
    return 0;
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 844 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 844 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 844 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -