oj.uz

Submission #75376

# Submission time Handle Problem Language Result Execution time Memory
75376 2018-09-09T13:22:15 Z damien_g Vudu (COCI15_vudu) C++14
42 / 140
 1000 ms 66560 KB 
#include <cstdio>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

const ll INF = 1LL << 60;

struct Node
{
    int nb;
    Node *left, *right;
    
    Node() {};
    Node(int _nb, Node* _left, Node* _right): nb(_nb), left(_left), right(_right) {};
};

Node* root;

void add(Node *act, int value, int l = 0, int r = (1 << 20))
{
    if(r != l)
    {
        if(value <= (l+r)/2)
        {
            if(!act->left)
                act->left = new Node(0, NULL, NULL);
            add(act->left, value, l, (l+r)/2);
        }
        else
        {
            if(!act->right)
                act->right = new Node(0, NULL, NULL);
            add(act->right, value, (l+r)/2+1, r);
        }
    }
    act->nb++;
}

ll rsq(Node* node, int l, int r, int nl = 0, int nr = (1 << 20))
{
    if((r < nl) || (nr < l))
        return 0;
    
    if((l <= nl) && (nr <= r))
        return node->nb;
    
    ll a = (node->left)?rsq(node->left, l, r, nl, (nl+nr)/2):0;
    ll b = (node->right)?rsq(node->right, l, r, (nl+nr)/2+1, nr):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(0, NULL, NULL);
    
    ll ans = 0, S = 0;
    set<ll> sums;
    sums.insert(0);
    for(int i = 0; i < N; i++)
    {
        S += a[i];
        sums.insert(S);
    }
    
    int k = 0;
    map<ll, int> hash;
    for(ll u : sums)
        hash[u] = k++;
    
    sums.clear();
    add(root, hash[0]);
    
    S = 0;
    for(int i = 0; i < N; i++)
    {
        S += a[i];
        ans += rsq(root, 0, hash[S]);
        add(root, hash[S]);
    }
    
    printf("%lld\n", ans);
    return 0;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
vudu.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a[i]);
         ~~~~~^~~~~~~~~~~~~~~
vudu.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &P);
     ~~~~~^~~~~~~~~~~~

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1272 KB Output is correct
2 Correct 9 ms 1308 KB Output is correct
3 Correct 20 ms 1308 KB Output is correct
4 Runtime error 786 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Execution timed out 1081 ms 66560 KB Time limit exceeded
6 Runtime error 691 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 635 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 663 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 664 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 624 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)