oj.uz

Submission #480299

# Submission time Handle Problem Language Result Execution time Memory
480299 2021-10-15T14:48:28 Z MOUF_MAHMALAT Zagrade (COI17_zagrade) C++14
0 / 100
 237 ms 71492 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;
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;
        if(c=='(')
            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;
        //cout<<i<<m<<endl;
        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()-1;
        ans+=r-l+1;
    }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

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