Submission #60693

#	Time	Username	Problem	Language	Result	Execution time	Memory
60693		aryanc403	Vudu (COCI15_vudu)	C++14	42 / 140	1076 ms	66560 KiB

vudu

//Invitation to ICO Preparatory Contest #1
//ICOP1901
//mean array

/************************************************************************************************************************************************************************************
  *                                                                                                                                                                                  *
   *                                                                                                                                                                                  *
    *  ****************    **************    *               *    ****************    *           *    ****************    *              *    ****************    ****************    *
     *  *              *    *            *    *               *    *              *    **          *    *                   *              *    *              *                   *    *
      *  *              *    *            *    *               *    *              *    * *         *    *                   *              *    *              *                   *    *
       *  *              *    *            *    *               *    *              *    *  *        *    *                   *              *    *              *                   *    *
        *  *              *    *            *    *               *    *              *    *   *       *    *                   *              *    *              *                   *    *
         *  *              *    *            *    *               *    *              *    *    *      *    *                   *              *    *              *                   *    *
          *  ****************    **************    *****************    ****************    *     *     *    *                   ****************    *              *    ****************    *
           *  *              *    *  *                      *            *              *    *      *    *    *                                  *    *              *                   *    *
            *  *              *    *    *                    *            *              *    *       *   *    *                                  *    *              *                   *    *
             *  *              *    *      *                  *            *              *    *        *  *    *                                  *    *              *                   *    *
              *  *              *    *        *                *            *              *    *         * *    *                                  *    *              *                   *    *
               *  *              *    *          *              *            *              *    *          **    *                                  *    *              *                   *    *
                *  *              *    *            *            *            *              *    *           *    ****************                   *    ****************    ****************    *
                 *                                                                                                                                                                                  *
                  *                                                                                                                                                                                  *
                   ************************************************************************************************************************************************************************************/

#pragma warning(disable:4996)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")

#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
#define MAX 100002
#define PI 3.1415926535897932384626433832795
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;

const lli INF = 0xFFFFFFFFFFFFFFFL;
const lli mod = 1000000007L;

    lli T,n,i,m,j,k,in,cnt,l,sz;
    vi a,b,zz;
    set<lli> s;
    vi :: iterator it;
    node *root;
    //priority_queue < lli , vector < lli > , cmp > pq;// min priority_queue .

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)
{
    //cout<<endl<<"insert "<<n<<endl;
    node *nd=root;
    while(nd->val!=n)
    {
        if(nd->val>n)
        {
      //      cout<<"add "<<nd->val<<" left"<<endl;
            nd->nl++;
            nd=nd->left;
        }
        else
        {
        //    cout<<"add "<<nd->val<<" right"<<endl;
            nd->nr++;
            nd=nd->right;
        }
    }
    nd->nroot++;
//    cout<<"add "<<nd->val<<" nroot"<<endl<<endl;
}

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;
}

void preorder(node *nd)
{
    if(nd==NULL)
        return;
    preorder(nd->left);
    cout<<nd->val<<" ";
    preorder(nd->right);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    scanf(" %lld",&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)
    {
        in=zz[i];
        sum+=in-k;
        a.pb(sum);
        s.insert(sum);
    }
    //for(auto &x:a)
      //  cout<<x<<" ";
    //cout<<endl;
    for(auto &x:s)
    {
        sz++;
        b.pb(x);
    }
    root = bst(0,sz-1);
    //cout<<root->val;
    //preorder(root);
    //cout<<endl;
    //return 0;
    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]);
        //cout<<a[i]<<" "<<query(a[i])<<endl;
    }
    cnt=n*(n+1)/2-cnt;
    printf("%lld",cnt);
    return 0;
}

Compilation message (stderr)

vudu.cpp:25:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)
 
vudu.cpp:26:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
vudu.cpp: In function 'int main()':
vudu.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %lld",&n);
     ~~~~~^~~~~~~~~~~~
vudu.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %lld",&in);
         ~~~~~^~~~~~~~~~~~~
vudu.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %lld",&k);
     ~~~~~^~~~~~~~~~~~

• Subtask 1: 42 / 140