Submission #946668

#TimeUsernameProblemLanguageResultExecution timeMemory
946668NourWaelVudu (COCI15_vudu)C++17
56 / 140
470 ms65536 KiB
#include <bits/extc++.h> #define int long long using namespace std; using namespace __gnu_pbds; int const mxN = 1e6; int a[mxN + 1]; int seg[3*mxN]; map<int,int> val; int get ( int node, int l, int r, int ind) { if(ind<l) return 0; if(r-1<=ind) return seg[node]; int m = (l+r) / 2; return get(node*2+1, l, m, ind) + get(node*2+2, m, r, ind); } void update ( int node, int l, int r, int ind) { if(ind<l || ind>=r) return; if(l==r-1 && l==ind) { seg[node] += 1; return; } int m = (l+r) / 2; update(node*2+1, l, m, ind), update(node*2+2, m, r, ind); seg[node] = seg[node*2+1] + seg[node*2+2]; } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n,p, ans = 0, ind = 0; cin>>n; for(int i=0; i<n; i++) cin>>a[i]; cin>>p; vector<int> st; st.push_back(p); for(int i=0; i<n; i++) { a[i] += (i? a[i-1]:0); int x = a[i] - p*i; st.push_back(x); } sort(st.begin(),st.end()); val[st[0]] = 0; for(int i=1; i<st.size(); i++) { if(st[i]==st[i-1]) continue; ind++; val[st[i]] = ind; } int pw = (1<<(__lg(ind-1)+1)); update(0,0,pw, val[p]); for(int i=0; i<n; i++) { int x = a[i] - p*i; x = val[x]; ans += get(0,0,pw, x); update(0,0,pw,x); } cout<<ans; return 0; }

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:43:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    for(int i=1; i<st.size(); i++) {
      |                 ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...