답안 #60701

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60701 2018-07-24T14:35:34 Z aryanc403 Vudu (COCI15_vudu) C++14
42 / 140
1000 ms 66560 KB
#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);
     ~~~~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 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