Submission #872030

#TimeUsernameProblemLanguageResultExecution timeMemory
872030Hyojin역사적 조사 (JOI14_historical)C++17
100 / 100
215 ms7240 KiB
#include <bits/stdc++.h> using namespace std; #define bit(n,i) ((n>>i)&1) #define all(a) (a).begin(),(a).end() #define pb push_back #define ep emplace_back #define pii pair<int,int> #define piii pair<int,pii> #define fi first #define se second #define ll long long #define debug(x) cerr << #x << ' ' << x << '\n' #define dbg(x) cerr<<#x<<' '<<x<<' ' const int base=31; const int MOD=1e9+7; const int N=1e5+5; const int B=sqrt(N); vector<int>f; int n,q,a[N],timeDfs; pii mp[N]; ll cur=0,pre=0; void add(int x) { if (mp[x].fi!=timeDfs) { mp[x]={timeDfs,0}; } mp[x].se++; cur=max(cur,1ll*f[x]*mp[x].se); } void erase(int x) { mp[x].se--; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Shiho freopen("izumi_shiho_supremacy.in","r", stdin); freopen("izumi_shiho_supremacy.out","w", stdout); #endif cin>>n>>q; for (int i=1;i<=n;i++) { cin>>a[i]; f.pb(a[i]); } sort(all(f)); f.erase(unique(all(f)),f.end()); for (int i=1;i<=n;i++) a[i]=lower_bound(all(f),a[i])-f.begin(); vector<ll>ans(q); vector<array<int,3>>queries(q); for (int i=0;i<q;i++) { int l,r; cin>>l>>r; queries[i]={l,r,i}; } sort(all(queries),[&](array<int,3>x,array<int,3>y){ if (x[0]/B!=y[0]/B) return x[0]<y[0]; return x[1]<y[1]; }); int preblock=-1; int preR=-1; for (auto [l,r,id]:queries) { int idL=l/B; int idR=r/B; if (idL!=preblock) { ++timeDfs; preblock=idL; pre=cur=0; preR=(idL+1)*B; } if (idL==idR) { pre=cur; for (int i=l;i<=r;i++) add(a[i]); ans[id]=cur; cur=pre; for (int i=l;i<=r;i++) erase(a[i]); } else { for (;preR<=r;preR++) add(a[preR]); pre=cur; for (int i=l;i<=(idL+1)*B-1;i++) add(a[i]); ans[id]=cur; cur=pre; for (int i=l;i<=(idL+1)*B-1;i++) erase(a[i]); } } for (int i=0;i<q;i++) cout<<ans[i]<<"\n"; return 0; } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...