Submission #476421

#TimeUsernameProblemLanguageResultExecution timeMemory
476421nekiDiversity (CEOI21_diversity)C++14
64 / 100
7077 ms18648 KiB
#include <bits/stdc++.h> #define ll long long #define loop(i, a, b) for(ll i=a;i<b;++i) #define pool(i, a, b) for(ll i=a-1;i>=b;--i) #define fore(i, a) for(auto&& i:a) #define fi first #define se second #define ps(a) push_back(a) #define pb(a) pop_back(a) #define eb(...) emplace_back(__VA_ARGS__) #define sc scanf #define vc vector #define lb lower_bound #define ub upper_bound #define all(a) a.begin(), a.end() #define llmax LLONG_MAX/2 #define llmin -LLONG_MAX/2 using namespace std; #define mn 500100 #define par pair<ll, ll> #define ld long double #define mod 1000000007 vc<ll> a; ll cnt[300100]; set<ll> act; void add(ll i){ if(cnt[a[i]]==0)act.insert(a[i]); ++cnt[a[i]]; } void rem(ll i){ --cnt[a[i]]; if(cnt[a[i]]==0) act.erase(a[i]); } ll getans(){ ll sum=0; vc<ll> cs; fore(v, act) sum+=cnt[v], cs.ps(cnt[v]); sort(all(cs)); ll ret=0; vc<ll> pre(2, 0); loop(i, 0, cs.size()){ ret+=pre[i%2] * (sum-cs[i]-pre[i%2]); pre[i%2]+=cs[i]; ret+=cs[i] * (sum-cs[i]); ret+=(cs[i] * cs[i] + cs[i])/2; } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll n, q;cin >> n >> q; a.resize(n);loop(i, 0, n) cin >> a[i]; vc<array<ll, 3>> que(q); loop(i, 0, q){ cin >> que[i][0] >> que[i][1];--que[i][0], --que[i][1];} loop(i, 0, q) que[i][2]=i; const ll m=550; sort(all(que), [&](array<ll, 3> a, array<ll, 3> b){ if(a[0]/m==b[0]/m) return a[1]<b[1]; return a[0]<b[0]; }); vc<ll> ans(q); ll l=0, r=-1; loop(i, 0, q){ ll ql=que[i][0], qr=que[i][1]; while(r<qr) add(++r); while(r>qr) rem(r--); while(l<ql) rem(l++); while(l>ql) add(--l); ans[que[i][2]]=getans(); } loop(i, 0, q) cout << ans[i]<<endl; }

Compilation message (stderr)

diversity.cpp: In function 'long long int getans()':
diversity.cpp:3:35: 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]
    3 | #define loop(i, a, b) for(ll i=a;i<b;++i)
......
   44 |     loop(i, 0, cs.size()){
      |          ~~~~~~~~~~~~~~~           
diversity.cpp:44:5: note: in expansion of macro 'loop'
   44 |     loop(i, 0, cs.size()){
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...