oj.uz

Submission #480308

# Submission time Handle Problem Language Result Execution time Memory
480308 2021-10-15T15:22:35 Z MOUF_MAHMALAT Zagrade (COI17_zagrade) C++14
30 / 100
 436 ms 69060 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
ll n,p[300009][20],lg[300009],x,ans;
char c[300009];
vector<vector<ll> >v;
ll op(ll l,ll r)
{
    ll k=lg[r-l+1];
    return min(p[l][k],p[r-(1<<k)+1][k]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    v.resize(2*n+9);
    for(ll i=2; i<=n; i++)
        lg[i]=lg[i>>1]+1;
    for(ll i=1; i<=n; i++)
    {
        cin>>c[i];
        if(c[i]=='(')
            p[i][0]++;
        else
            p[i][0]--;
        p[i][0]+=p[i-1][0];
        v[p[i][0]+n].push_back(i);
    }
    for(ll i=1; i<n; i++)
        cin>>x>>x;
    for(ll j=1; j<=lg[n]; j++)
        for(ll i=1; i+(1<<j)<=n+1; i++)
            p[i][j]=min(p[i][j-1],p[i+(1<<(j-1))][j-1]);
    for(ll i=1; i<=n; i++)
    {
        if(p[i][0]-p[i-1][0]==-1)
            continue;
        ll l=i,r=n+1,m;
        while(r-l>1)
        {
            m=(l+r)>>1;
            x=op(i,m);
            if(x<p[i][0]-1)
                r=m;
            else
                l=m;
        }
        m=l;
        x=p[i][0]-1+n;
        l=upper_bound(all(v[x]),i)-v[x].begin();
        r=upper_bound(all(v[x]),m)-v[x].begin();
        ans+=r-l;
    }
    v.clear();
    v.resize(2*n+9);
    for(ll i=1; i<=n; i++)
    {
        if(c[i]=='(')
            p[i][0]=-1;
        else
            p[i][0]=1;
        p[i][0]+=p[i-1][0];
        v[p[i][0]+n].push_back(i);
    }
    for(ll j=1; j<=lg[n]; j++)
        for(ll i=1; i+(1<<j)<=n+1; i++)
            p[i][j]=min(p[i][j-1],p[i+(1<<(j-1))][j-1]);
    for(ll i=1; i<=n; i++)
    {
        if(p[i][0]-p[i-1][0]==-1)
            continue;
        ll l=i,r=n+1,m;
        while(r-l>1)
        {
            m=(l+r)>>1;
            x=op(i,m);
            if(x<p[i][0]-1)
                r=m;
            else
                l=m;
        }
        m=l;
        x=p[i][0]-1+n;
        l=upper_bound(all(v[x]),i)-v[x].begin();
        r=upper_bound(all(v[x]),m)-v[x].begin();
        ans+=r-l;
    }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 67584 KB Output is correct
2 Correct 376 ms 69060 KB Output is correct
3 Correct 380 ms 67620 KB Output is correct
4 Correct 371 ms 68560 KB Output is correct
5 Correct 362 ms 67440 KB Output is correct
6 Correct 436 ms 67880 KB Output is correct
7 Correct 386 ms 67344 KB Output is correct
8 Correct 400 ms 67780 KB Output is correct
9 Correct 352 ms 67508 KB Output is correct
10 Correct 288 ms 68620 KB Output is correct
11 Correct 319 ms 68612 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -