oj.uz

Submission #780918

# Submission time Handle Problem Language Result Execution time Memory
780918 2023-07-12T14:35:51 Z vjudge1 Election (BOI18_election) C++17
82 / 100
 73 ms 10356 KB 
#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int long long
using namespace std;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);
const int maxn=1e5+7;
const int mod=1e9+9;
int n,a[maxn],q,b,c;
char x;
struct node
{
   int sum,pre,suf,seg;
}ST[4*maxn];
node operator +(node a,node b)
{
    node res;
    res.pre=max(a.sum+b.pre,a.pre);
    res.suf=max(a.suf+b.sum,b.suf);
    res.sum=a.sum+b.sum;
    res.seg=max({a.seg,b.seg,a.suf+b.pre});
    return res;
}
void construct(int id,int cl,int cr)
{
    if(cl==cr)
    {
        ST[id].pre=max(0LL,a[cl]);
        ST[id].suf=max(0LL,a[cl]);
        ST[id].seg=max(0LL,a[cl]);
        ST[id].sum=a[cl];
        return;
    }
    int mid=(cl+cr)/2;
    construct(2*id,cl,mid);
    construct(2*id+1,mid+1,cr);
    ST[id]=ST[2*id]+ST[2*id+1];
}
node query(int id,int cl,int cr,int l,int r)
{
    if(cl>r||cr<l) return {0,0,0,0};
    if(cl>=l&&cr<=r) return ST[id];
    int mid=(cl+cr)/2;
    return query(2*id,cl,mid,l,r)+query(2*id+1,mid+1,cr,l,r);
}
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if(x=='C') a[i]=1;
        else a[i]=-1;
    }
    construct(1,1,n);
    cin>>q;
    while(q--)
    {
        cin>>b>>c;
        node w=query(1,1,n,b,c);
        cout<<w.seg-w.sum<<"\n";
    }
}

Compilation message

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(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 51 ms 10208 KB Output is correct
7 Correct 49 ms 10220 KB Output is correct
8 Correct 51 ms 10216 KB Output is correct
9 Correct 48 ms 10168 KB Output is correct
10 Correct 57 ms 10164 KB Output is correct
11 Correct 52 ms 10356 KB Output is correct
12 Correct 52 ms 10280 KB Output is correct
13 Correct 52 ms 10264 KB Output is correct
14 Correct 53 ms 10264 KB Output is correct
15 Correct 73 ms 10188 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 51 ms 10208 KB Output is correct
7 Correct 49 ms 10220 KB Output is correct
8 Correct 51 ms 10216 KB Output is correct
9 Correct 48 ms 10168 KB Output is correct
10 Correct 57 ms 10164 KB Output is correct
11 Correct 52 ms 10356 KB Output is correct
12 Correct 52 ms 10280 KB Output is correct
13 Correct 52 ms 10264 KB Output is correct
14 Correct 53 ms 10264 KB Output is correct
15 Correct 73 ms 10188 KB Output is correct
16 Incorrect 2 ms 1244 KB Output isn't correct
17 Halted 0 ms 0 KB -