oj.uz

Submission #779976

# Submission time Handle Problem Language Result Execution time Memory
779976 2023-07-12T04:43:39 Z 이동현(#10007) 역사적 조사 (JOI14_historical) C++17
0 / 100
 7 ms 1140 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

const int NS = (int)1e5 + 4;
int n, q;
int B = 1000;
int a[NS];
int srt[NS];
int cnt[NS], ans[NS];
struct ran{
    int l, r, id;
    bool operator<(const ran&R)const{
        return l / B < R.l / B || (l / B == R.l / B && ((r < R.r) ^ (l / B % 2)));
    }
}que[NS];

struct Data{
    long long val;
    int id;
    Data(){}
    Data(long long val, int id):val(val), id(id){}
    bool operator<(const Data&r)const{
        return val < r.val;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        srt[i] = a[i];
    }
    sort(srt, srt + n);
    for(int i = 0; i < n; ++i){
        a[i] = lower_bound(srt, srt + n, a[i]) - srt;
    }
    for(int i = 0; i < q; ++i){
        cin >> que[i].l >> que[i].r;
        --que[i].l, --que[i].r;
        que[i].id = i;
    }
    sort(que, que + q);

    priority_queue<Data> pq;
    int r = -1, l = 0;
    for(int i = 0; i < q; ++i){
        while(r < que[i].r){
            ++r;
            ++cnt[a[r]];
            pq.push(Data((long long)srt[a[r]] * cnt[a[r]], a[r]));
        }
        while(l > que[i].l){
            --l;
            ++cnt[a[l]];
            pq.push(Data((long long)srt[a[l]] * cnt[a[l]], a[l]));
        }
        while(r > que[i].r){
            --cnt[a[r]];
            pq.push(Data((long long)srt[a[r]] * cnt[a[r]], a[r]));
            --r;
        }
        while(l < que[i].l){
            --cnt[a[l]];
            pq.push(Data((long long)srt[a[l]] * cnt[a[l]], a[l]));
            ++l;
        }

        long long mx = 0;
        map<int, int> ct;
        for(int j = que[i].l; j <= que[i].r; ++j){
            ++ct[a[j]];
            mx = max(mx, (long long)srt[a[j]] * ct[a[j]]);
        }

        while((long long)srt[pq.top().id] * cnt[pq.top().id] != pq.top().val){
            pq.pop();
        }

        ans[que[i].id] = mx;
    }

    for(int i = 0; i < q; ++i){
        cout << ans[i] << '\n';
    }
    
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 496 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 7 ms 992 KB Output is correct
8 Incorrect 7 ms 1140 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -