oj.uz

답안 #861659

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861659 2023-10-16T15:49:07 Z iskhakkutbilim Election (BOI18_election) C++17
0 / 100
 11 ms 63064 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define ll long long
 
struct Node{
    ll sum, pref, suff, ans;
};
 
int n, arr[(int)5e5 + 10];
 
struct SegmentTree{
    vector<Node> sgt;
    SegmentTree(int n){
        sgt.resize(4 * n);
    }
    Node merge(Node a, Node b){
        return { a.sum + b.sum, max(a.pref, a.sum + b.pref), max(b.suff, a.suff + b.sum), 
		max({0LL, a.pref + b.suff}) };
    }
    void build(int k = 1, int l = 0, int r = n - 1){
        if(l == r){
            sgt[k] = { arr[l], max(0, arr[l]), max(0, arr[l]), max(arr[l], 0) };
            return;
        }
        int m = (l + r) / 2;
        build(k * 2, l, m);
        build(k * 2 + 1, m + 1, r);
        sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
    }
    Node get(int k, int l, int r, int i, int j){
        if (l > j || r < i) return {0, 0, 0, 0};
        if (i <= l && r <= j) return sgt[k];
        int m = (l + r) / 2;
        return merge(get(k * 2, l, m, i, j), get(k * 2 + 1, m + 1, r, i, j));
    }
 
} sgt(5e5);
 
main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) arr[i] = (s[i] == 'C' ? -1 : 1);
    sgt.build();
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << sgt.get(1, 0, n - 1, --x, --y).ans << '\n';
    }
}

Compilation message

election.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main() {
      | ^~~~

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 63064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 63064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 63064 KB Output isn't correct
2 Halted 0 ms 0 KB -