제출 #795728

#제출 시각아이디문제언어결과실행 시간메모리
795728NguyenKhangIzbori (COCI22_izbori)C++17
0 / 110
80 ms11456 KiB
//#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("bmi,bmi2,lzcnt,popcnt") //#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native") //#pragma expected_value //#pragma isolated_call //#pragma disjoint #include<bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //using namespace __gnu_pbds; using namespace std; #define int long long //#define double long double #define Fi first #define Se second #define Rep(i,a,b) for (int i=a;i<=b;++i) #define Repu(i,b,a) for (int i=b;i>=a;--i) #define pb push_back #define ms(a,i) memset(a,i,sizeof(a)) #define sz size() #define mp make_pair #define endl '\n' #define sef setprecision(6)<<fixed #define cer cout<<"cak"<<endl; typedef pair<int,int> ii; typedef vector<int> vi; typedef vector<double> va; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<va> vva; //const double EPS=1e-9; const double PI=acos(-1); const long long oo=1e18; const int MN=2e5+5; const int mod=1e9+7; using cd=complex<double>; //typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> index_set; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int cunt = 400; int n; int a[MN]; vi s[MN]; int cnt; int ans = 0; int type[MN]; void compress() { vii v; v.pb(mp(0,0)); Rep(i,1,n) v.pb(mp(a[i],i)); sort(v.begin(),v.end()); Rep(i,1,n) { if(v[i].Fi != v[i-1].Fi) ++cnt; a[v[i].Se] = cnt; s[cnt].pb(v[i].Se); } } void light() { Rep(i,1,n) { int mx = 0; Rep(j,i,min(i+cunt,n)) { int color = a[j]; if(type[color] == 0) continue; int temp = lower_bound(s[color].begin(), s[color].end(), j) - lower_bound(s[color].begin(), s[color].end(), i); if(a[i] == color) temp ++; if(temp > mx) mx = temp; if(mx*2 > j-i+1) ++ans; } } } struct Fenwick_tree { int n; vi b; void init(int _n) { n=_n; b.resize(n+5,0); } void clear() { Rep(i,1,n) b[i] = 0; } void updatePoint(int u,int val) { while(u<=n) { b[u] += val; u += (u&(-u)); } } int getPrefix(int u) { int ans=0; while(u) { ans += b[u]; u -= (u&(-u)); } return ans; } }; Fenwick_tree bit; void heavy(int color) { bit.clear(); bit.updatePoint(n+1, 1); int pre = 0; Rep(i,1,n) { if(a[i] == color) ++pre; ans += bit.getPrefix(2*pre - i + n + 1); bit.updatePoint(2*pre - i + n + 2, 1); } } signed main() { //freopen(".inp","r",stdin); freopen(".out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; Rep(i,1,n) cin>>a[i]; compress(); // light Rep(i,1,cnt) { if(s[i].sz <= cunt) type[i] = 1; } light(); // heavy bit.init(3*n); Rep(i,1,cnt) { if(type[i]) continue; heavy(i); } cout<<ans; }

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

Main.cpp: In function 'int main()':
Main.cpp:144:14: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  144 |   if(s[i].sz <= cunt) type[i] = 1;
      |      ~~~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...