oj.uz

Submission #13779

# Submission time Handle Problem Language Result Execution time Memory
13779 2015-04-01T09:48:14 Z Namnamseo 역사적 조사 (JOI14_historical) C++
5 / 100
 4000 ms 6612 KB 
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>

using namespace std;

int imp[100010];
int cnt[100010];
typedef long long ll;
ll  ans[100010];
int in;
int data[100010];
int bck;

struct qr{int ind,l,r; bool operator<(const qr& other) const { return l/bck==other.l/bck?r<other.r:l<other.l; }; } query[100010];

int n,q;

set<ll> s;

void add(int val){
    int ind=lower_bound(imp,imp+in,val)-imp;
    if(cnt[ind]) s.erase(((long long)cnt[ind])*val);
    ++cnt[ind]; s.insert(((long long)cnt[ind])*val);
}

void rem(int val){
    int ind=lower_bound(imp,imp+in,val)-imp;
    s.erase(((long long)cnt[ind])*val);
    --cnt[ind]; if(cnt[ind]) s.insert(((long long)cnt[ind])*val);
}

int main()
{
    scanf("%d%d",&n,&q); int i; for(i=1;i<=n;++i) scanf("%d",data+i),imp[i]=data[i];
    bck=n/sqrt(q);
    sort(imp,imp+n);in=unique(imp,imp+n)-imp;
    int a,b;
    for(i=0;i<q;++i) scanf("%d%d",&a,&b),query[i].ind=i,query[i].l=a,query[i].r=b;
    sort(query,query+q);
    int l=query[0].l, r=query[0].r;
    for(i=l;i<=r;++i) add(data[i]);
    ans[query[0].ind]=*(--s.end());
    for(i=1;i<q;++i){
        while(query[i].l<=l-1) add(data[--l]);
        while(r+1<=query[i].r) add(data[++r]);
        while(l<query[i].l) rem(data[l++]);
        while(query[i].r<r) rem(data[r--]);
        ans[query[i].ind]=*(--s.end());
    }
    for(i=0;i<q;++i) printf("%lld\n",ans[i]);
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 0 ms 4368 KB Output is correct
3 Correct 1 ms 4368 KB Output is correct
4 Correct 0 ms 4368 KB Output is correct
5 Correct 0 ms 4368 KB Output is correct
6 Correct 0 ms 4368 KB Output is correct
7 Correct 0 ms 4368 KB Output is correct
8 Correct 1 ms 4368 KB Output is correct
9 Correct 0 ms 4368 KB Output is correct
10 Correct 0 ms 4368 KB Output is correct
11 Correct 0 ms 4368 KB Output is correct
12 Correct 0 ms 4368 KB Output is correct
13 Correct 0 ms 4368 KB Output is correct
14 Correct 0 ms 4368 KB Output is correct
15 Correct 0 ms 4368 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 3 ms 4368 KB Output is correct
3 Correct 8 ms 4368 KB Output is correct
4 Correct 24 ms 4368 KB Output is correct
5 Correct 70 ms 4368 KB Output is correct
6 Correct 123 ms 4368 KB Output is correct
7 Correct 139 ms 4368 KB Output is correct
8 Incorrect 101 ms 4368 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 0 ms 4368 KB Output is correct
3 Correct 0 ms 4368 KB Output is correct
4 Correct 0 ms 4368 KB Output is correct
5 Correct 0 ms 4368 KB Output is correct
6 Correct 3 ms 4368 KB Output is correct
7 Correct 6 ms 4368 KB Output is correct
8 Correct 12 ms 4368 KB Output is correct
9 Correct 25 ms 4368 KB Output is correct
10 Correct 21 ms 4368 KB Output is correct
11 Correct 103 ms 4368 KB Output is correct
12 Correct 86 ms 4368 KB Output is correct
13 Correct 89 ms 4368 KB Output is correct
14 Correct 128 ms 4368 KB Output is correct
15 Correct 129 ms 4368 KB Output is correct
16 Incorrect 143 ms 6612 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 4368 KB Output is correct
2 Correct 1268 ms 4368 KB Output is correct
3 Correct 3027 ms 4500 KB Output is correct
4 Execution timed out 4000 ms 4892 KB Program timed out
5 Halted 0 ms 0 KB -