Submission #60696

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60696	2018-07-24T14:29:23 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
#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;

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) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %lld",&n);
     ~~~~~^~~~~~~~~~~~
vudu.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %lld",&in);
         ~~~~~^~~~~~~~~~~~~
vudu.cpp:119: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	10 ms	1272 KB	Output is correct
2	Correct	7 ms	1272 KB	Output is correct
3	Correct	7 ms	1272 KB	Output is correct
4	Execution timed out	1070 ms	66560 KB	Time limit exceeded
5	Execution timed out	1022 ms	66560 KB	Time limit exceeded
6	Execution timed out	1008 ms	66560 KB	Time limit exceeded
7	Execution timed out	1031 ms	66560 KB	Time limit exceeded
8	Execution timed out	1028 ms	66560 KB	Time limit exceeded
9	Execution timed out	1070 ms	66560 KB	Time limit exceeded
10	Execution timed out	1018 ms	66560 KB	Time limit exceeded