제출 #1011244

#제출 시각아이디문제언어결과실행 시간메모리
10112440pt1mus23Izbori (COCI22_izbori)C++14
110 / 110
1832 ms55888 KiB
/* not my sol, edu */ #pragma GCC optimize("O3", "inline") #include <bits/stdc++.h> using namespace std; #define ins insert #define pb push_back #define int long long int #define pii pair<int, int> #define endl '\n' #define drop(x) cout<<(x)<<endl; return; #define all(x) x.begin(),x.end() const int mod = 1e9 +7, sze = 2e5+10, inf = LLONG_MAX, prime = 1453; int arr[sze]; int brr[sze]; int dac(int l,int r){ if(l==r){ return 1; } if(l>r){ return 0; } int ans=0; int mid = (l+r)/2; set<int> cand; map<int,int> cnt; for(int i = mid-1;i>=l;i--){ ++cnt[arr[i]]; if(cnt[arr[i]]> (mid-i)/2){ cand.ins(arr[i]); } } cnt.clear(); for(int i = mid;i<=r;i++){ ++cnt[arr[i]]; if(cnt[arr[i]]>(i-mid+1)/2){ cand.ins(arr[i]); } } for(auto v:cand){ for(int i=l;i<=r;i++){ if(arr[i]==v){ brr[i]=+1; } else{ brr[i]=-1; } } cnt.clear(); int sum=0; ++cnt[0]; for(int i=l;i<mid;i++){ sum+=brr[i]; ++cnt[sum]; } int upto = (r-l+1); for(int i = -upto;i<=upto;i++){ cnt[i]+=cnt[i-1]; } for(int i = mid;i<=r;i++){ sum+=brr[i]; ans+=cnt[sum-1]; } } // cout<<l<<" "<<r<<" "<<ans<<endl; return ans + dac(l,mid-1) + dac(mid+1,r); } void mal(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>arr[i]; } cout<<dac(1,n)<<endl; } signed main() { cin.tie(0)->sync_with_stdio(0); clock_t z = clock(); int tt = 1; // cin>>tt; while(tt--){ mal(); } // cerr<<(double)(clock() - z) / CLOCKS_PER_SEC <<endl; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:86:13: warning: unused variable 'z' [-Wunused-variable]
   86 |     clock_t z = clock();
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...