Submission #42365

#	Time	Username	Problem	Language	Result	Execution time	Memory
42365		nickyrio	역사적 조사 (JOI14_historical)	C++14	40 / 100	4086 ms	11684 KiB

historic

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1001000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

using namespace std;

int x[N], n, q;
struct data {
    int l, r, p;
}query[N];
int BLOCK_SIZE;

map<int, long long> cnt;
multiset<long long> remain;
long long res[N];

void Up(int p, int val) {
    if (remain.find(cnt[p] * p) != remain.end()) remain.erase(remain.find(cnt[p] * p));
    cnt[p] += val;
    remain.insert(cnt[p] * p);
}

int main() {
    scanf("%d %d", &n, &q);
    FOR(i, 1, n) scanf("%d", &x[i]);
    BLOCK_SIZE = sqrt(n);
    REP(i, q) {
        scanf("%d %d", &query[i].l, &query[i].r);
        query[i].p = i;
    }
    sort(query, query + q, [] (const data &a, const data &b) {
        int ba = a.l / BLOCK_SIZE;
        int bb = b.l / BLOCK_SIZE;
        return ba == bb ? a.r < b.r : ba < bb;
    });
    int l = 1, r = 0;
    REP(i, q) {
        while (r < query[i].r) Up(x[++r], 1);
        while (l > query[i].l) Up(x[--l], 1);
        while (r > query[i].r) Up(x[r--], -1);
        while (l < query[i].l) Up(x[l++], -1);
        res[query[i].p] = *remain.rbegin();
    }
    REP(i, q) printf("%lld\n",res[i]);
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:34:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
historic.cpp:35:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &x[i]);
                                    ^
historic.cpp:38:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &query[i].l, &query[i].r);
                                                 ^

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