Submission #164842

#TimeUsernameProblemLanguageResultExecution timeMemory
164842ly20역사적 조사 (JOI14_historical)C++17
100 / 100
1536 ms243216 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 112345; const int sz = sqrt(MAXN) + 10; int v[MAXN]; long long marc[MAXN]; long long mrk[sz][MAXN]; int sq[MAXN]; map <int, int> mp; set <int> s; set <int> :: iterator it; int ini[sz], fim[sz]; long long rs[sz][sz]; long long IM1P2[MAXN]; int main() { int n, q; scanf("%d %d", &n, &q); int par = (n - 1) / sz + 1; for(int i = 0; i < n; i++) { scanf("%d", &v[i]); s.insert(v[i]); } int temp = 0; for(it = s.begin(); it != s.end(); it++) { mp[*it] = temp; IM1P2[temp] = *it; temp++; } //for(int i = 0; i < 10; i++) printf("%d IM1P2 = %lld\n", i, IM1P2[i]); for(int i = 0; i < n; i++) { v[i] = mp[v[i]]; sq[i] = i / sz; //printf("v = %d i = %d sq = %d IM1P2 = %lld\n", v[i], i, sq[i], IM1P2[v[i]]); } for(int i = 0; i < par; i++) { //printf("oi\n"); ini[i] = i * sz; fim[i] = min(n - 1, (i + 1) * sz - 1); //printf("2\n"); } long long resp; for(int i = 0; i < par; i++) { resp = 0; for(int j = ini[i]; j < n; j++) { mrk[i][v[j]]++; //printf("%d %lld\n", v[j], IM1P2[v[j]]); if(mrk[i][v[j]] * IM1P2[v[j]] > resp) { resp = mrk[i][v[j]] * IM1P2[v[j]]; } if(j == fim[sq[j]]) { rs[i][sq[j]] = resp; //printf("%d - %d : %lld\n", i, sq[j], resp); } } } for(int i = 0; i < q; i++) { //for(int j = 0; j < n; j++) printf("%d - %d\n", j, sq[j]); int a, b; scanf("%d %d", &a, &b); a--; b--; //printf("%d == %d\n%d %d\n", sq[a], sq[b], a, b); if(sq[a] == sq[b]) { //printf("%d %d\n", a + 1, b + 1); long long resp = 0; for(int j = a; j <= b; j++) { marc[v[j]]++; //printf("%lld apareceu %lld vezes\n", IM1P2[v[j]], marc[v[j]]); resp = max(resp, marc[v[j]] * IM1P2[v[j]]); } printf("%lld\n", resp); for(int j = a; j <= b; j++) marc[v[j]]--; } else { long long resp = 0; if(sq[a] != sq[b] - 1) resp = rs[sq[a] + 1][sq[b] - 1]; for(int j = a; j <= fim[sq[a]]; j++) { marc[v[j]]++; if((marc[v[j]] + mrk[sq[a] + 1][v[j]] - mrk[sq[b]][v[j]]) * IM1P2[v[j]] > resp) { resp = (marc[v[j]] + mrk[sq[a] + 1][v[j]] - mrk[sq[b]][v[j]]) * IM1P2[v[j]]; } } for(int j = b; j >= ini[sq[b]]; j--) { marc[v[j]]++; if((marc[v[j]] + mrk[sq[a] + 1][v[j]] - mrk[sq[b]][v[j]]) * IM1P2[v[j]] > resp) { resp = (marc[v[j]] + mrk[sq[a] + 1][v[j]] - mrk[sq[b]][v[j]]) * IM1P2[v[j]]; } } printf("%lld\n", resp); for(int j = a; j <= fim[sq[a]]; j++) { marc[v[j]]--; } for(int j = b; j >= ini[sq[b]];j--) { marc[v[j]]--; } } } }

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i]);
   ~~~~~^~~~~~~~~~~~~
historic.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b); a--; b--;
   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...