Submission #480308

#	Time	Username	Problem	Language	Result	Execution time	Memory
480308		MOUF_MAHMALAT	Zagrade (COI17_zagrade)	C++14	30 / 100	436 ms	69060 KiB

zagrade

#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
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60