oj.uz

Submission #780414

# Submission time Handle Problem Language Result Execution time Memory
780414 2023-07-12T08:54:07 Z 이동현(#10007) 역사적 조사 (JOI14_historical) C++17
0 / 100
 1 ms 340 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, SZ = (int)5e6 + 4;
int n, q;
int B = 400;
int a[NS];
int srt[NS];
int cnt[NS];
long long 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];

long long val[SZ], id[SZ];
int hn;
long long imsi;

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

    register int i, l, r;

    cin >> n >> q;
    for(i = 0; i < n; ++i){
        cin >> a[i];
        srt[i] = a[i];
    }
    sort(srt, srt + n);
    for(i = 0; i < n; ++i){
        a[i] = lower_bound(srt, srt + n, a[i]) - srt;
    }
    for(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);

    r = -1, l = 0;
    int now, nxt;
    for(i = 0; i < q; ++i){
        while(r < que[i].r){
            ++r;
            ++cnt[a[r]];

            val[++hn] = (long long)srt[a[r]] * cnt[a[r]];
            id[hn] = a[r];

            for(now = hn; now > 1 && val[now] > val[nxt = (now >> 1)]; ){
                imsi = val[now], val[now] = val[nxt], val[nxt] = imsi;
                imsi = id[now], id[now] = id[nxt], id[nxt] = imsi;
                now = nxt;
            }
        }
        while(l > que[i].l){
            --l;
            ++cnt[a[l]];
            val[++hn] = (long long)srt[a[l]] * cnt[a[l]];
            id[hn] = a[l];

            for(now = hn; now > 1 && val[now] > val[nxt = (now >> 1)]; ){
                imsi = val[now], val[now] = val[nxt], val[nxt] = imsi;
                imsi = id[now], id[now] = id[nxt], id[nxt] = imsi;
                now = nxt;
            }
        }
        while(r > que[i].r){
            --cnt[a[r]];
            val[++hn] = (long long)srt[a[r]] * cnt[a[r]];
            id[hn] = a[r];
            --r;
        }
        while(l < que[i].l){
            --cnt[a[l]];
            val[++hn] = (long long)srt[a[l]] * cnt[a[l]];
            id[hn] = a[l];
            ++l;
        }

        int sv;
        while(hn > 1 && (long long)srt[id[1]] * cnt[id[1]] != val[1]){
            sv = id[1];
            imsi = val[1], val[1] = val[hn], val[hn] = imsi;
            imsi = id[1], id[1] = id[hn], id[hn] = imsi;
            --hn;
            for(now = 1; (nxt = now << 1) + 1 <= hn;){
                if(val[nxt] > val[now] && val[nxt] > val[nxt + 1]){
                    imsi = val[now], val[now] = val[nxt], val[nxt] = imsi;
                    imsi = id[now], id[now] = id[nxt], id[nxt] = imsi;
                    now = nxt;
                }
                else if(val[nxt + 1] > val[now]){
                    imsi = val[now], val[now] = val[nxt + 1], val[nxt + 1] = imsi;
                    imsi = id[now], id[now] = id[nxt + 1], id[nxt + 1] = imsi;
                    now = nxt + 1;
                }
                else{
                    break;
                }
            }
            if((nxt = now << 1) <= hn && val[nxt] > val[now]){
                imsi = val[now], val[now] = val[nxt], val[nxt] = imsi;
                imsi = id[now], id[now] = id[nxt], id[nxt] = imsi;
            }

            if(cnt[sv]){
                val[++hn] = (long long)srt[sv] * cnt[sv];
                id[hn] = sv;

                for(now = hn; now > 1 && val[now] > val[nxt = (now >> 1)]; ){
                    imsi = val[now], val[now] = val[nxt], val[nxt] = imsi;
                    imsi = id[now], id[now] = id[nxt], id[nxt] = imsi;
                    now = nxt;
                }
            }
        }

        ans[que[i].id] = val[1];
    }

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

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:29:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   29 |     register int i, l, r;
      |                  ^
historic.cpp:29:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   29 |     register int i, l, r;
      |                     ^
historic.cpp:29:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   29 |     register int i, l, r;
      |                        ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 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 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 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 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -