oj.uz

Submission #760553

# Submission time Handle Problem Language Result Execution time Memory
760553 2023-06-17T18:53:15 Z vjudge1 Election (BOI18_election) C++17
100 / 100
 1930 ms 82096 KB 
#include <bits/stdc++.h>
#define ve vector
#define vi vector<int>
#define vii vector<ii>
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
#define INF 1e9+7
#define pb push_back
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
    tree_order_statistics_node_update>;
const int MOD = 1e9+7;
const int nax = 5e5+5;
void readio(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}
vi st[nax*4]{vi(4)};
vi merge(vi a, vi b){
    vi res(4);
    res[0] = a[0]+b[0];
    res[1] = max(a[1], b[1]+a[0]);
    res[2] = max(b[2], a[2]+b[0]);
    res[3] = max(max(max(a[3]+b[0], b[3]+a[0]),0), a[1]+b[2]);
    return res;
}
string s;
void build(int v, int l, int r){
    if(l == r){
        int a = (s[l] == 'T'), b = a;
        if(b == 0) b--;
        st[v] = {b,a,a,a};
        return;
    }
    int md = (l+r)/2;
    build(v*2,l,md);
    build(v*2+1,md+1,r);
    st[v] = merge(st[v*2], st[v*2+1]);
    //cout << l << " " << r << ' ' << st[v][3] << endl;
}
vi query(int v, int l, int r, int i, int j){
    if(i > r || j < l) return {0,0,0,0};
    if(i <= l && r <= j) return st[v];
    int md = (l+r)/2;
    return merge(query(v*2,l,md, i , j), query(v*2+1, md+1, r, i , j));
}
int main()
{
    optimise;
    int n;
    cin >> n;
    cin >> s;
    build(1,0,n-1);
    int q;
    cin >> q;
    while(q--){
        int l,r;
        cin >> l >> r;
        l--,r--;
        cout << query(1,0,n-1, l, r)[3] << endl;
    }
}

Compilation message

election.cpp: In function 'void readio()':
election.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47316 KB Output is correct
2 Correct 27 ms 47316 KB Output is correct
3 Correct 27 ms 47356 KB Output is correct
4 Correct 28 ms 47400 KB Output is correct
5 Correct 27 ms 47316 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47316 KB Output is correct
2 Correct 27 ms 47316 KB Output is correct
3 Correct 27 ms 47356 KB Output is correct
4 Correct 28 ms 47400 KB Output is correct
5 Correct 27 ms 47316 KB Output is correct
6 Correct 232 ms 51988 KB Output is correct
7 Correct 210 ms 51992 KB Output is correct
8 Correct 224 ms 51896 KB Output is correct
9 Correct 182 ms 51924 KB Output is correct
10 Correct 209 ms 51860 KB Output is correct
11 Correct 258 ms 52060 KB Output is correct
12 Correct 227 ms 52044 KB Output is correct
13 Correct 257 ms 52000 KB Output is correct
14 Correct 206 ms 52004 KB Output is correct
15 Correct 225 ms 52104 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47316 KB Output is correct
2 Correct 27 ms 47316 KB Output is correct
3 Correct 27 ms 47356 KB Output is correct
4 Correct 28 ms 47400 KB Output is correct
5 Correct 27 ms 47316 KB Output is correct
6 Correct 232 ms 51988 KB Output is correct
7 Correct 210 ms 51992 KB Output is correct
8 Correct 224 ms 51896 KB Output is correct
9 Correct 182 ms 51924 KB Output is correct
10 Correct 209 ms 51860 KB Output is correct
11 Correct 258 ms 52060 KB Output is correct
12 Correct 227 ms 52044 KB Output is correct
13 Correct 257 ms 52000 KB Output is correct
14 Correct 206 ms 52004 KB Output is correct
15 Correct 225 ms 52104 KB Output is correct
16 Correct 1869 ms 81068 KB Output is correct
17 Correct 1604 ms 81092 KB Output is correct
18 Correct 1797 ms 80984 KB Output is correct
19 Correct 1490 ms 80624 KB Output is correct
20 Correct 1816 ms 80064 KB Output is correct
21 Correct 1878 ms 81792 KB Output is correct
22 Correct 1919 ms 81844 KB Output is correct
23 Correct 1843 ms 82096 KB Output is correct
24 Correct 1795 ms 81612 KB Output is correct
25 Correct 1930 ms 81128 KB Output is correct