Submission #902173

#TimeUsernameProblemLanguageResultExecution timeMemory
902173IsamIzbori (COCI22_izbori)C++17
40 / 110
3013 ms6984 KiB
#include<bits/stdc++.h> using namespace std; constexpr int sz = 300005; int N, A[sz]; long long pref[sz], tree[sz]; unordered_set<int> st; inline void update(int pos, long long val){ while(pos <= N + 5){ tree[pos] += val; pos += (pos & (-pos)); } return; } long long get_ans(int l, int r){ if(l != 1) return get_ans(1, r) - get_ans(1, l - 1); long long res(0); while(r > 0){ res += tree[r]; r -= (r & (-r)); } return res; } signed main(){ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> N; for(register int i = 1; i <= N; ++i){ cin >> A[i]; st.insert(A[i]); } long long ans(0); for(auto &tot : st){ for(register int i = 1; i <= N + 10; ++i) tree[i] = 0; long long mn = N + 5; for(register int i = 1; i <= N; ++i){ pref[i] = pref[i - 1] + (tot == A[i] ? 1 : -1); mn = min(mn, pref[i]); } mn = abs(mn) + 5; update(mn, 1); for(register int i = 1; i <= N ;++i){ pref[i] += mn; update(pref[i], 1); ans += get_ans(1, pref[i] - 1); } } cout << ans << '\n'; return 0; } /* 1 1 2 1 2 -1 -1 1 -1 1 */

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:32:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   32 |  for(register int i = 1; i <= N; ++i){
      |                   ^
Main.cpp:38:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   38 |   for(register int i = 1; i <= N + 10; ++i) tree[i] = 0;
      |                    ^
Main.cpp:40:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   40 |   for(register int i = 1; i <= N; ++i){
      |                    ^
Main.cpp:46:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   46 |   for(register int i = 1; i <= N ;++i){
      |                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...