oj.uz

Submission #439723

# Submission time Handle Problem Language Result Execution time Memory
439723 2021-06-30T16:16:36 Z cpp219 Election (BOI18_election) C++14
100 / 100
 704 ms 28004 KB 
#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e5 + 9;
const ll inf = 1e9 + 7;
string s;
ll n,Q,l,r;

struct Node{
    ll pre,suf,sum,ans;
};
Node st[4*N];

Node combine(Node L,Node R){
    Node kq;
    kq.sum = L.sum + R.sum;
    kq.pre = max(L.pre,L.sum + R.pre);
    kq.suf = max(R.suf,R.sum + L.suf);
    kq.ans = max(L.pre + R.suf,max(L.ans + R.sum,L.sum + R.ans));
    return kq;
}

void build(ll id,ll l,ll r){
    if (l == r){
        if (s[l] == 'C') st[id] = {0,0,-1,0};
        else st[id] = {1,1,1,1}; return;
    }
    ll mid = (l + r)/2;
    build(id*2,l,mid); build(id*2 + 1,mid + 1,r);
    st[id] = combine(st[id*2],st[id*2 + 1]);
}

Node spare = {0,0,0,0};

Node Get(ll id,ll l,ll r,ll u,ll v){
    if (v < l||r < u) return spare;
    if (u <= l&&r <= v) return st[id];
    ll mid = (l + r)/2;
    return combine(Get(id*2,l,mid,u,v),Get(id*2 + 1,mid + 1,r,u,v));
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>s; s = " " + s; build(1,1,n);
    cin>>Q;
    while(Q--){
        cin>>l>>r;
        cout<<Get(1,1,n,l,r).ans<<"\n";
    }
}

Compilation message

election.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
election.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
election.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
election.cpp: In function 'void build(int, int, int)':
election.cpp:34:9: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   34 |         else st[id] = {1,1,1,1}; return;
      |         ^~~~
election.cpp:34:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   34 |         else st[id] = {1,1,1,1}; return;
      |                                  ^~~~~~
election.cpp: In function 'int main()':
election.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 73 ms 5744 KB Output is correct
7 Correct 63 ms 5720 KB Output is correct
8 Correct 67 ms 5684 KB Output is correct
9 Correct 60 ms 5724 KB Output is correct
10 Correct 65 ms 5568 KB Output is correct
11 Correct 69 ms 5848 KB Output is correct
12 Correct 75 ms 5824 KB Output is correct
13 Correct 66 ms 5780 KB Output is correct
14 Correct 65 ms 5840 KB Output is correct
15 Correct 85 ms 5824 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 73 ms 5744 KB Output is correct
7 Correct 63 ms 5720 KB Output is correct
8 Correct 67 ms 5684 KB Output is correct
9 Correct 60 ms 5724 KB Output is correct
10 Correct 65 ms 5568 KB Output is correct
11 Correct 69 ms 5848 KB Output is correct
12 Correct 75 ms 5824 KB Output is correct
13 Correct 66 ms 5780 KB Output is correct
14 Correct 65 ms 5840 KB Output is correct
15 Correct 85 ms 5824 KB Output is correct
16 Correct 672 ms 26916 KB Output is correct
17 Correct 538 ms 26720 KB Output is correct
18 Correct 624 ms 26800 KB Output is correct
19 Correct 503 ms 26248 KB Output is correct
20 Correct 654 ms 26096 KB Output is correct
21 Correct 694 ms 27880 KB Output is correct
22 Correct 698 ms 27768 KB Output is correct
23 Correct 670 ms 28004 KB Output is correct
24 Correct 662 ms 27748 KB Output is correct
25 Correct 704 ms 27096 KB Output is correct