답안 #237332

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237332	2020-06-06T02:16:38 Z	mohamedsobhi777	Vudu (COCI15_vudu)	C++14	56 / 140	1000 ms	64228 KB

vudu

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 7;

int n, k;
int a[N];


vector<long long> srtd ; 
unordered_map<long long, int > mp ;
int bit[N] ;
int tree[4*N] ;

int read_int()
{
        char r;
        bool start = false, neg = false;
        int ret = 0;
        while (true)
        {
                r = getchar();
                if ((r - '0' < 0 || r - '0' > 9) && r != '-' && !start)
                {
                        continue;
                }
                if ((r - '0' < 0 || r - '0' > 9) && r != '-' && start)
                {
                        break;
                }
                if (start)
                        ret *= 10;
                start = true;
                if (r == '-')
                        neg = true;
                else
                        ret += r - '0';
        }
        if (!neg)
                return ret;
        else
                return -ret;
}

void update(int node , int L , int R , int ix , int v){
        if(L == R){
                tree[node]+=v ; 
                return ; 
        }

        int mid = (L + R) >> 1 ; 

        if(ix <=mid){
                update(node*2+1 , L , mid , ix , v) ;
        }
        else{
                update(node*2+2 , mid+1 , R, ix , v) ; 
        }
        tree[node] = tree[node*2+1]  + tree[node*2+2] ;
}

int query(int node , int L , int R , int l , int r){
        if(l > R || r < L ) return 0 ; 
        if(L>=l && R<=r)
                return tree[node] ; 
        int mid = (L+R) >> 1; 
        int s1 = query(node*2+1 , L , mid , l , r) ;
        int s2 = query(node*2+2 , mid+1 , R , l ,r) ; 
        return s1 + s2 ; 
}

int t =1 ; 

int com(long long x){
        int ret = mp[x] ; 
        if(ret)return ret ; 
        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);

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

        k = read_int(); 
        
        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;

        update(0 ,1 , N , com(0) , 1) ;  
        for (int i = 0; i < n; i++)
        {
                pre += a[i];
                int aux = com(pre) ; 
                ans+= query(0 , 1 , N , 1 , aux)  ;
                update(0 ,1 ,N , aux , 1) ; 
        }
        cout << ans;
        return 0;
}

Subtask #1

56.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	896 KB	Output is correct
2	Correct	8 ms	768 KB	Output is correct
3	Correct	8 ms	640 KB	Output is correct
4	Execution timed out	1085 ms	64228 KB	Time limit exceeded
5	Correct	710 ms	35792 KB	Output is correct
6	Execution timed out	1046 ms	51536 KB	Time limit exceeded
7	Execution timed out	1046 ms	53200 KB	Time limit exceeded
8	Execution timed out	1039 ms	47032 KB	Time limit exceeded
9	Execution timed out	1098 ms	64128 KB	Time limit exceeded
10	Execution timed out	1053 ms	51796 KB	Time limit exceeded