제출 #1069047

#제출 시각아이디문제언어결과실행 시간메모리
1069047AndreyDiversity (CEOI21_diversity)C++14
38 / 100
7045 ms251252 KiB
#include<bits/stdc++.h> using namespace std; long long pr[300001][101]; vector<long long> haha(300001); vector<long long> br(300001); vector<pair<pair<long long,long long>,long long>> bruh[300001]; const long long k = 100; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long n,q,l,r; cin >> n >> q; for(long long i = 1; i <= 100; i++) { for(long long j = 0; j <= n; j++) { pr[j][i] = j*(j+1)/2; if(j >= i) { pr[j][i]+=pr[j-i][i]; } } } for(long long i = 1; i <= n; i++) { cin >> haha[i]; } for(long long i = 0; i < q; i++) { cin >> l >> r; bruh[l/k].push_back({{r,l},i}); } vector<long long> ans(q); for(long long i = 0; i < n; i++) { sort(bruh[i].begin(),bruh[i].end()); } for(long long i = 0; i < n; i++) { if(i*k > n) { break; } for(long long j = 0; j < br.size(); j++) { br[j] = 0; } long long y = bruh[i].size(); vector<long long> wow(k+1); for(long long j = 0; j < bruh[i].size(); j++) { if(bruh[i][j].first.first >= (i+1)*k) { y = j; break; } r = bruh[i][j].first.first,l = bruh[i][j].first.second; for(long long j = l; j <= r; j++) { wow[br[haha[j]]]--; br[haha[j]]++; wow[br[haha[j]]]++; } long long pl = 0,pr = 0,sb = 0; for(long long j = 1; j <= k; j++) { for(long long x = 0; x < wow[j]; x++) { if(pl > pr) { swap(pr,pl); } long long m = r-l+1; sb+=m*(m+1)/2; sb-=pl*(pl+1)/2; long long c = m-pl-j; sb-=c*(c+1)/2; pl+=j; } } ans[bruh[i][j].second] = sb; for(long long j = l; j <= r; j++) { br[haha[j]] = 0; } for(long long j = 0; j <= k; j++) { wow[j] = 0; } } vector<long long> wut(0); for(long long j = (i+1)*k; j <= n; j++) { if(br[haha[j]] < k) { wow[br[haha[j]]]--; wow[br[haha[j]]+1]++; } else if(br[haha[j]] == k) { wow[br[haha[j]]]--; wut.push_back(haha[j]); } br[haha[j]]++; while(y < bruh[i].size() && bruh[i][y].first.first == j) { vector<long long> troll(k+1); for(long long z = 0; z <= k; z++) { troll[z] = wow[z]; } r = bruh[i][y].first.first,l = bruh[i][y].first.second; for(long long z = l; z < (i+1)*k; z++) { if(br[haha[z]] < k) { wow[br[haha[z]]]--; wow[br[haha[z]]+1]++; } else if(br[haha[z]] == k) { wow[br[haha[z]]]--; wut.push_back(haha[z]); } br[haha[z]]++; } long long ql = 0,qr = 0,sb = 0,m = (r-l+1); for(long long j = 1; j <= k; j++) { long long a = wow[j]; if(ql > qr) { swap(ql,qr); } sb+=(m*(m+1)/2)*a; long long d = (a+1)/2; if(d > 0) { sb-=pr[ql+j*(d-1)][j]; if(ql >= j) { sb+=pr[ql-j][j]; } long long c = m-ql-j; sb-=pr[c][j]; if(c >= d*j) { sb+=pr[c-d*j][j]; } } d = a/2; swap(ql,qr); if(d > 0) { sb-=pr[ql+j*(d-1)][j]; if(ql >= j) { sb+=pr[ql-j][j]; } long long c = m-ql-j; sb-=pr[c][j]; if(c >= d*j) { sb+=pr[c-d*j][j]; } } swap(ql,qr); ql+=j*((a+1)/2); qr+=j*(a/2); } vector<long long> banana(0); for(long long z = 0; z < wut.size(); z++) { banana.push_back(br[wut[z]]); } sort(banana.begin(),banana.end()); for(long long z = 0; z < banana.size(); z++) { long long a = banana[z]; if(ql > qr) { swap(ql,qr); } sb+=m*(m+1)/2; sb-=ql*(ql+1)/2; long long c = m-ql-a; sb-=c*(c+1)/2; ql+=a; } ans[bruh[i][y].second] = sb; for(long long z = l; z < (i+1)*k; z++) { br[haha[z]]--; } while(!wut.empty() && br[wut[wut.size()-1]] <= k) { wut.pop_back(); } for(long long z = 0; z <= k; z++) { wow[z] = troll[z]; } y++; } } } for(long long i = 0; i < q; i++) { cout << ans[i] << "\n"; } return 0; }

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

diversity.cpp: In function 'int main()':
diversity.cpp:40:32: 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]
   40 |         for(long long j = 0; j < br.size(); j++) {
      |                              ~~^~~~~~~~~~~
diversity.cpp:45:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(long long j = 0; j < bruh[i].size(); j++) {
      |                              ~~^~~~~~~~~~~~~~~~
diversity.cpp:89:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             while(y < bruh[i].size() && bruh[i][y].first.first == j) {
      |                   ~~^~~~~~~~~~~~~~~~
diversity.cpp:143:40: 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]
  143 |                 for(long long z = 0; z < wut.size(); z++) {
      |                                      ~~^~~~~~~~~~~~
diversity.cpp:147:40: 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]
  147 |                 for(long long z = 0; z < banana.size(); z++) {
      |                                      ~~^~~~~~~~~~~~~~~
#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...