답안 #75366

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75366 2018-09-09T12:53:28 Z damien_g Vudu (COCI15_vudu) C++14
42 / 140
391 ms 66560 KB
#include <cstdio>

using namespace std;

typedef long long ll;

const ll INF = 1LL << 60;

struct Node
{
    ll l, r;
    int nb;
    Node *left, *right;
    
    Node() {};
    Node(ll _l, ll _r, int _nb, Node* _left, Node* _right): l(_l), r(_r), nb(_nb), left(_left), right(_right) {};
};

Node* root;

ll half(ll k)
{
    if(k >= 0)
        return k/2;
    return -(-k+1)/2;
}

void add(Node *act, ll value)
{
    /*printf("%p, Add, %lld\n", act, value);
    printf("%lld %lld\n\n", act->l, act->r);*/
    
    if(act->r != act->l)
    {
        if(value <= half(act->l+act->r))
        {
            if(!act->left)
                act->left = new Node(act->l, half(act->l+act->r), 0, NULL, NULL);
            add(act->left, value);
        }
        else
        {
            if(!act->right)
                act->right = new Node(half(act->l+act->r)+1, act->r, 0, NULL, NULL);
            add(act->right, value);
        }
    }
    act->nb++;
}

ll rsq(Node* node, ll l, ll r)
{
    if((r < node->l) || (node->r < l))
        return 0;
    
    if((l <= node->l) && (node->r <= r))
        return node->nb;
    
    ll a = (node->left)?rsq(node->left, l, r):0;
    ll b = (node->right)?rsq(node->right, l, r):0;
    return a+b;
}

int N;
ll a[1 << 20];
ll P;

int main()
{
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%lld", &a[i]);
    scanf("%lld", &P);
    
    for(int i = 0; i < N; i++)
        a[i] -= P;
    
    root = new Node(-INF, INF, 0, NULL, NULL);
    add(root, 0);
    
    ll ans = 0, S = 0;
    for(int i = 0; i < N; i++)
    {
        S += a[i];
        //printf("OK\n");
        ans += rsq(root, -INF, S);
        //printf("OK\n");
        add(root, S);
        //printf("OK\n");
    }
    
    printf("%lld\n", ans);
    return 0;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
vudu.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a[i]);
         ~~~~~^~~~~~~~~~~~~~~
vudu.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &P);
     ~~~~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1528 KB Output is correct
2 Correct 11 ms 1528 KB Output is correct
3 Correct 8 ms 1528 KB Output is correct
4 Runtime error 391 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 262 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 345 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 341 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 298 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 334 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 306 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)