oj.uz

답안 #237324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237324 2020-06-06T01:47:18 Z mohamedsobhi777 Vudu (COCI15_vudu) C++14
56 / 140
 1000 ms 65540 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 7;

int n, k;
int a[N];


vector<long long> srtd ; 
map<long long, int > mp ;
int bit[N] ;

void add(int x){
        for(;x < N ;x += x&-x ){
                bit[x] ++ ; 
        }
}

int get(int x){
        if(x < 0 ) return 0; 
        int ret =0 ; 
        for(;x;x-=x&-x){
                ret+=bit[x] ;
        }
        return ret ; 
}

int t =1 ; 

int com(long long x){
        if(mp[x]){
                return mp[x] ;
        }
        mp[x] = t++ ; 
        return t-1 ; 
}

void init(){
        srtd.push_back(0) ; 
        sort(srtd.begin() , srtd.end()) ; 

        for(int i = 0 ; i < (int) srtd.size() ;i++){
                com(srtd[i]) ;
        }
}

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);

        cin >> n;
        for (int i = 0; i < n; i++)
        {
                cin >> a[i];
        }

        cin >> k;
        
        long long sum = 0 ;

        for (int i = 0; i < n; i++)
        {
                a[i] -= k;
                sum+= a[i] ; 
                srtd.push_back(sum) ;
        }

        init() ;
        
        long long ans = 0;
        long long pre = 0;
        add(com(0)) ; 
        for (int i = 0; i < n; i++)
        {
                pre += a[i];
                ans+= get(com(pre)) ;
                add(com(pre)) ; 
        }
        cout << ans;
        return 0;
}

Subtask #1
56.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 896 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 8 ms 768 KB Output is correct
4 Runtime error 568 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Correct 810 ms 43324 KB Output is correct
6 Runtime error 765 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 603 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Execution timed out 1092 ms 60884 KB Time limit exceeded
9 Runtime error 580 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 580 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)