Submission #42353

#	Time	Username	Problem	Language	Result	Execution time	Memory
42353		dqhungdl	역사적 조사 (JOI14_historical)	C++14	100 / 100	191 ms	6488 KiB

historic

#include <bits/stdc++.h>
using namespace std;

struct data
{
    int l,r,id;
};

typedef pair<int,int> ii;
const int block=320;
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++)
                      ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60