Submission #42347

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

historic

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

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

typedef pair<int,int> ii;
const int block=300;
data Q[100005];
int n,T,a[100005],Pre[100005];
int64_t rs[100005],Free[100005];
ii b[100005];
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];
        b[i]=ii(a[i],i);
    }
    sort(b+1,b+n+1);
    Pre[b[1].second]=1;
    int 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>>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[Pre[r]]>0)
                s.erase(s.find(Free[Pre[r]]));
            Free[Pre[r]]+=a[r];
            s.insert(Free[Pre[r]]);
        }
        while(l>Q[i].l)
        {
            l--;
            if(Free[Pre[l]]>0)
                s.erase(s.find(Free[Pre[l]]));
            Free[Pre[l]]+=a[l];
            s.insert(Free[Pre[l]]);
        }
        while(r>Q[i].r)
        {
            s.erase(s.find(Free[Pre[r]]));
            Free[Pre[r]]-=a[r];
            if(Free[Pre[r]]>0)
                s.insert(Free[Pre[r]]);
            r--;
        }
        while(l<Q[i].l)
        {
            s.erase(s.find(Free[Pre[l]]));
            Free[Pre[l]]-=a[l];
            if(Free[Pre[l]]>0)
                s.insert(Free[Pre[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