oj.uz

답안 #313409

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
313409 2020-10-16T00:05:08 Z Vince729 Election (BOI18_election) C++11
0 / 100
 159 ms 262144 KB 
#include<iostream>
#include<algorithm>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
    int l_max, r_max, tot, ans;

    Node operator+(Node b) {
        Node ret;
        ret.l_max = max(l_max, b.l_max + tot);
        ret.r_max = max(r_max + b.tot, b.r_max);
        ret.tot = tot + b.tot;
        ret.ans = max(max(ans + b.tot, b.ans + tot), l_max + b.r_max);
        return ret;
    }
};

Node segtree[2000001];
char s[500001];
int n;

void build(int node = 1, int l = 1, int r = n) {
    if (l == r) {
        if (s[l] == 'T') segtree[node] = {1, 1, 1, 1};
        else segtree[node] = {0, 0, -1, 0};
    } else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    }
}

Node query(int a, int b, int node = 1, int l = 1, int r = n) {
    if (l > b || r < a) return {0, 0, 0, 0};
    if (l >= a && r <= b) return segtree[node];
    int mid = (l + r) / 2;
    return query(a, b, node * 2, l, mid) + query(a, b, node * 2 + 1, mid + 1, r);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("elections.in", "r", stdin);
    freopen("elections.out", "w", stdout);
    cin >> n;
    FOR(i, 1, n + 1) cin >> s[i];
    build();
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b).ans << '\n';
    }
    return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   46 |     freopen("elections.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   47 |     freopen("elections.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 159 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 159 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 159 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -