Submission #42352

#TimeUsernameProblemLanguageResultExecution timeMemory
42352dqhungdl역사적 조사 (JOI14_historical)C++14
5 / 100
4 ms1068 KiB
#include <bits/stdc++.h> using namespace std; struct data { int l,r,id; }; typedef pair<int,int> ii; const int block=2; int n,T,a[100005],Pre[100005]; int64_t rs[100005],Free[100005]; ii b[100005]; vector<data> Q[350]; bool cmp(data x1,data x2) { return x1.r<x2.r; } int main() { ios_base::sync_with_stdio(false); //freopen("TEST.INP","r",stdin); cin>>n>>T; for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=ii(a[i],i); } sort(b+1,b+n+1); Pre[b[1].second]=1; int l,r,Count=1; for(int i=2;i<=n;i++) if(b[i].first>b[i-1].first) Pre[b[i].second]=++Count; else Pre[b[i].second]=Count; for(int i=1;i<=T;i++) { cin>>l>>r; Q[(l-1)/block+1].push_back({l,r,i}); } for(int i=1;i<=(n-1)/block+1;i++) { sort(Q[i].begin(),Q[i].end(),cmp); for(int j=1;j<=Count;j++) Free[j]=0; int tmp=i*block+1; int64_t res=0; for(int j=0;j<Q[i].size();j++) { int l=Q[i][j].l; int r=Q[i][j].r; int id=Q[i][j].id; if(r<=i*block) { for(int t=l;t<=r;t++) { Free[Pre[t]]+=a[t]; rs[id]=max(rs[id],Free[Pre[t]]); } for(int t=l;t<=r;t++) Free[Pre[t]]-=a[t]; } else { while(tmp<=r) { Free[Pre[tmp]]+=a[tmp]; res=max(res,Free[Pre[tmp]]); tmp++; } rs[id]=res; for(int t=l;t<=i*block;t++) { Free[Pre[t]]+=a[t]; rs[id]=max(rs[id],Free[Pre[t]]); } for(int t=l;t<=i*block;t++) Free[Pre[t]]-=a[t]; } } } for(int i=1;i<=T;i++) cout<<rs[i]<<"\n"; }

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<Q[i].size();j++)
                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...