Submission #60701

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60701	2018-07-24T14:35:34 Z	aryanc403	Vudu (COCI15_vudu)	C++14	42 / 140	1000 ms	66560 KB

vudu

#include<iostream>
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
typedef long long int lli;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
 
typedef struct _node{
    lli val,nl,nr,nroot;
    struct _node *left,*right;
}node;
 
    lli T,n,i,m,j,k,in,cnt,l,sz;
    vi a,b,zz;
    set<lli> s;
    vi :: iterator it;
    node *root;
 
node *makeNode(lli n)
{
    node *nd= (node *) malloc(sizeof(node));
    nd->val=n;
    nd->left=nd->right=NULL;
    nd->nl=nd->nr=nd->nroot=0;
    return nd;
}
 
node* bst(lli l,lli r)
{
    if(l==r)
        return makeNode(b[l]);
    if(l>r)
        return NULL;
    lli m=l+(r-l)/2;
    node* nd=makeNode(b[m]);
    nd->left=bst(l,m-1);
    nd->right=bst(m+1,r);
    return nd;
}
 
void insert(lli n)
{
    node *nd=root;
    while(nd->val!=n)
    {
        if(nd->val>n)
        {
            nd->nl++;
            nd=nd->left;
        }
        else
        {
            nd->nr++;
            nd=nd->right;
        }
    }
    nd->nroot++;
}
 
void del(lli n)
{
    node *nd=root;
    while(nd->val!=n)
    {
        if(nd->val>n)
        {
            nd->nl--;
            nd=nd->left;
        }
        else
        {
            nd->nr--;
            nd=nd->right;
        }
    }
    nd->nroot--;
}
 
lli query(lli n)
{
    node *nd=root;
    lli cnt=0;
    while(nd->val!=n)
    {
        if(nd->val>n)
            nd=nd->left;
        else
        {
            cnt+=nd->nl+nd->nroot;
            nd=nd->right;
        }
    }
    cnt+=nd->nl;
    return cnt;
}
 
int main(void) {
    scanf(" %lld",&n);
    zz.clear();zz.reserve(n);
    fo(i,n)
    {
        scanf(" %lld",&in);
        zz.pb(in);
    }
    scanf(" %lld",&k);
    a.clear();a.reserve(n+4);
    lli sum=0;
    a.pb(0);
    s.insert(0);
    fo(i,n)
    {
        sum+=zz[i]-k;
        a.pb(sum);
        s.insert(sum);
    }
    for(auto &x:s)
    {
        sz++;
        b.pb(x);
    }
    root = bst(0,sz-1);
    for(i=0;i<=n;++i)
        insert(a[i]);
    lli cnt=0;
    for(i=0;i<n;++i)
    {
        del(a[i]);
        cnt+=query(a[i]);
    }
    cnt=n*(n+1)/2-cnt;
    printf("%lld",cnt);
    return 0;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %lld",&n);
     ~~~~~^~~~~~~~~~~~
vudu.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %lld",&in);
         ~~~~~^~~~~~~~~~~~~
vudu.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %lld",&k);
     ~~~~~^~~~~~~~~~~~

Subtask #1

42.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	1276 KB	Output is correct
2	Correct	9 ms	1284 KB	Output is correct
3	Correct	10 ms	1284 KB	Output is correct
4	Execution timed out	1081 ms	66560 KB	Time limit exceeded
5	Execution timed out	1100 ms	66560 KB	Time limit exceeded
6	Execution timed out	1012 ms	66560 KB	Time limit exceeded
7	Execution timed out	1035 ms	66560 KB	Time limit exceeded
8	Execution timed out	1066 ms	66560 KB	Time limit exceeded
9	Execution timed out	1014 ms	66560 KB	Time limit exceeded
10	Execution timed out	1030 ms	66560 KB	Time limit exceeded