Submission #60696

#TimeUsernameProblemLanguageResultExecution timeMemory
60696aryanc403Vudu (COCI15_vudu)C++14
42 / 140
1070 ms66560 KiB
#include<iostream> #include<bits/stdc++.h> #include<stdio.h> using namespace std; #define fo(i,n) for(i=0;i<(n);++i) #define pb push_back #define mp make_pair #define X first #define Y second #define MAX 100002 #define PI 3.1415926535897932384626433832795 typedef long long int lli; typedef pair<lli,lli> ii; typedef vector<ii> vii; typedef vector<lli> vi; typedef struct _node{ lli val,nl,nr,nroot; struct _node *left,*right; }node; const lli INF = 0xFFFFFFFFFFFFFFFL; const lli mod = 1000000007L; lli T,n,i,m,j,k,in,cnt,l,sz; vi a,b,zz; set<lli> s; vi :: iterator it; node *root; node *makeNode(lli n) { node *nd= (node *) malloc(sizeof(node)); nd->val=n; nd->left=nd->right=NULL; nd->nl=nd->nr=nd->nroot=0; return nd; } node* bst(lli l,lli r) { if(l==r) return makeNode(b[l]); if(l>r) return NULL; lli m=l+(r-l)/2; node* nd=makeNode(b[m]); nd->left=bst(l,m-1); nd->right=bst(m+1,r); return nd; } void insert(lli n) { node *nd=root; while(nd->val!=n) { if(nd->val>n) { nd->nl++; nd=nd->left; } else { nd->nr++; nd=nd->right; } } nd->nroot++; } void del(lli n) { node *nd=root; while(nd->val!=n) { if(nd->val>n) { nd->nl--; nd=nd->left; } else { nd->nr--; nd=nd->right; } } nd->nroot--; } lli query(lli n) { node *nd=root; lli cnt=0; while(nd->val!=n) { if(nd->val>n) nd=nd->left; else { cnt+=nd->nl+nd->nroot; nd=nd->right; } } cnt+=nd->nl; return cnt; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); scanf(" %lld",&n); zz.clear();zz.reserve(n); fo(i,n) { scanf(" %lld",&in); zz.pb(in); } scanf(" %lld",&k); a.clear();a.reserve(n+4); lli sum=0; a.pb(0); s.insert(0); fo(i,n) { sum+=zz[i]-k; a.pb(sum); s.insert(sum); } for(auto &x:s) { sz++; b.pb(x); } root = bst(0,sz-1); for(i=0;i<=n;++i) insert(a[i]); lli cnt=0; for(i=0;i<n;++i) { del(a[i]); cnt+=query(a[i]); } cnt=n*(n+1)/2-cnt; printf("%lld",cnt); return 0; }

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %lld",&n);
     ~~~~~^~~~~~~~~~~~
vudu.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %lld",&in);
         ~~~~~^~~~~~~~~~~~~
vudu.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %lld",&k);
     ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...