Submission #42345

#	Time	Username	Problem	Language	Result	Execution time	Memory
42345		dqhungdl	역사적 조사 (JOI14_historical)	C++14	40 / 100	4069 ms	11676 KiB

historic

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

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

const int block=300;
data Q[100005];
int n,T,a[100005];
int64_t rs[100005];
map<int,int64_t> Free;
multiset<int64_t> s;

bool cmp(data x1,data x2)
{
    if(x1.l/block==x2.l/block)
        return x1.r<x2.r;
    return x1.l/block<x2.l/block;
}

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];
    for(int i=1;i<=T;i++)
    {
        cin>>Q[i].l>>Q[i].r;
        Q[i].id=i;
    }
    sort(Q+1,Q+T+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=T;i++)
    {
        while(r<Q[i].r)
        {
            r++;
            if(Free[a[r]]>0)
                s.erase(s.find(Free[a[r]]));
            Free[a[r]]+=a[r];
            s.insert(Free[a[r]]);
        }
        while(l>Q[i].l)
        {
            l--;
            if(Free[a[l]]>0)
                s.erase(s.find(Free[a[l]]));
            Free[a[l]]+=a[l];
            s.insert(Free[a[l]]);
        }
        while(r>Q[i].r)
        {
            s.erase(s.find(Free[a[r]]));
            Free[a[r]]-=a[r];
            if(Free[a[r]]>0)
                s.insert(Free[a[r]]);
            r--;
        }
        while(l<Q[i].l)
        {
            s.erase(s.find(Free[a[l]]));
            Free[a[l]]-=a[l];
            if(Free[a[l]]>0)
                s.insert(Free[a[l]]);
            l++;
        }
        rs[Q[i].id]=*s.rbegin();
    }
    for(int i=1;i<=T;i++)
        cout<<rs[i]<<"\n";
}

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