Submission #1192630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192630		vnedu	역사적 조사 (JOI14_historical)	C++17	100 / 100	125 ms	6044 KiB

historic

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

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e5 + 10;
const int Q = 1e5 + 10;
const int lim = 400;
struct Query
{
    int l,r,id;
    Query() {}
    Query(int l, int r, int id) : l(l),r(r),id(id) {}
    bool operator < (const Query &S) const
    {
        return r<S.r;
    }
};
int n,a[N],cnt[N],numQuery,numBlock,poi[N];
vector<Query> bucket[N/lim+10];
vector<int> nen;
ll s=0,ans[Q];
void toggle(int id, int xxx)
{
    id=poi[id];
    cnt[id]+=xxx;
    maximize(s,nen[id]*1LL*cnt[id]);
}
void solve()
{
    cin>>n>>numQuery;
    numBlock=(n+lim-1)/lim;
    for(int i=1;i<=n;++i) cin>>a[i],nen.pb(a[i]);
    sort(all(nen));
    nen.erase(unique(all(nen)),nen.end());
    for(int i=1;i<=n;++i) poi[i]=lower_bound(all(nen),a[i])-nen.begin();
    for(int i=1;i<=numQuery;++i)
    {
        int l,r; cin>>l>>r;
        bucket[(l-1)/lim+1].pb(Query(l,r,i));
    }
    for(int block=1;block<=numBlock;++block)
    {
        sort(all(bucket[block]));
        s=0;
        memset(cnt,0,sizeof(cnt));
        int r=min(n,block*lim);
        int ptr=r-1;
        for(Query &cm : bucket[block])
        {
            if(cm.r<r)
            {
                for(int i=cm.l;i<=cm.r;++i) toggle(i,1);
                ans[cm.id]=s;
                for(int i=cm.l;i<=cm.r;++i) toggle(i,-1);
                s=0;
            }
            else
            {
                while(ptr<cm.r) toggle(++ptr,1);
                ll old=s;
                for(int i=cm.l;i<r;++i) toggle(i,1);
                ans[cm.id]=s;
                for(int i=cm.l;i<r;++i) toggle(i,-1);
                s=old;
            }
        }
    }
    for(int i=1;i<=numQuery;++i) cout<<ans[i]<<'\n';
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

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