Submission #237336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
237336	2020-06-06T02:31:49 Z	mohamedsobhi777	Vudu (COCI15_vudu)	C++14	140 / 140	298 ms	27968 KB

vudu

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 7;

int n, k;
int a[N];


vector<pair<long long , int > > srtd ; 

int bit[N] ;
int pos[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 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 ; 

void init(){
        srtd.push_back({0 , 0}) ; 
        sort(srtd.begin() , srtd.end()) ; 
        for(int i = 0 ; i < (int) srtd.size() ;i++){
                pos[srtd[i].second]  = i +1;
        }
}

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 , i +1}) ;
        }

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

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:97:19: warning: unused variable 'pre' [-Wunused-variable]
         long long pre = 0;
                   ^~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	768 KB	Output is correct
2	Correct	5 ms	640 KB	Output is correct
3	Correct	6 ms	640 KB	Output is correct
4	Correct	271 ms	26920 KB	Output is correct
5	Correct	156 ms	19020 KB	Output is correct
6	Correct	238 ms	23876 KB	Output is correct
7	Correct	298 ms	24900 KB	Output is correct
8	Correct	217 ms	21696 KB	Output is correct
9	Correct	277 ms	27968 KB	Output is correct
10	Correct	237 ms	24512 KB	Output is correct