Submission #42349

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

historic

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

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

typedef pair<int,int> ii;
const int block=350;
data Q[100005];
int n,T,a[100005],Pre[100005];
int64_t rs[100005],tree[400005];
ii b[100005];

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;
}

void Update(int k,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tree[k]+=val;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid)
        Update(2*k,l,mid,pos,val);
    else
        Update(2*k+1,mid+1,r,pos,val);
    tree[k]=max(tree[2*k],tree[2*k+1]);
}

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++;
            Update(1,1,Count,Pre[r],a[r]);
        }
        while(l>Q[i].l)
        {
            l--;
            Update(1,1,Count,Pre[l],a[l]);
        }
        while(r>Q[i].r)
        {
            Update(1,1,Count,Pre[r],-a[r]);
            r--;
        }
        while(l<Q[i].l)
        {
            Update(1,1,Count,Pre[l],-a[l]);
            l++;
        }
        rs[Q[i].id]=tree[1];
    }
    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