oj.uz

Submission #42365

# Submission time Handle Problem Language Result Execution time Memory
42365 2018-02-26T13:49:37 Z nickyrio 역사적 조사 (JOI14_historical) C++14
40 / 100
 4000 ms 11684 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 2 ms 404 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 ms 548 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 2 ms 620 KB Output is correct
15 Correct 2 ms 620 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 7 ms 620 KB Output is correct
3 Correct 18 ms 620 KB Output is correct
4 Correct 43 ms 620 KB Output is correct
5 Correct 105 ms 748 KB Output is correct
6 Correct 181 ms 876 KB Output is correct
7 Correct 224 ms 876 KB Output is correct
8 Correct 123 ms 876 KB Output is correct
9 Correct 132 ms 900 KB Output is correct
10 Correct 319 ms 1196 KB Output is correct
11 Correct 310 ms 1196 KB Output is correct
12 Correct 310 ms 1196 KB Output is correct
13 Correct 310 ms 1196 KB Output is correct
14 Correct 278 ms 1196 KB Output is correct
15 Correct 283 ms 1196 KB Output is correct
16 Correct 136 ms 1196 KB Output is correct
17 Correct 45 ms 1196 KB Output is correct
18 Correct 299 ms 1196 KB Output is correct
19 Correct 331 ms 1196 KB Output is correct
20 Correct 358 ms 1196 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1196 KB Output is correct
2 Correct 2 ms 1196 KB Output is correct
3 Correct 1 ms 1196 KB Output is correct
4 Correct 2 ms 1196 KB Output is correct
5 Correct 4 ms 1196 KB Output is correct
6 Correct 4 ms 1196 KB Output is correct
7 Correct 10 ms 1196 KB Output is correct
8 Correct 22 ms 1196 KB Output is correct
9 Correct 50 ms 1324 KB Output is correct
10 Correct 16 ms 1324 KB Output is correct
11 Correct 148 ms 3244 KB Output is correct
12 Correct 146 ms 3244 KB Output is correct
13 Correct 170 ms 3244 KB Output is correct
14 Correct 242 ms 5292 KB Output is correct
15 Correct 208 ms 7468 KB Output is correct
16 Correct 288 ms 11184 KB Output is correct
17 Correct 72 ms 11184 KB Output is correct
18 Correct 112 ms 11184 KB Output is correct
19 Correct 216 ms 11184 KB Output is correct
20 Correct 135 ms 11684 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 11684 KB Output is correct
2 Correct 2254 ms 11684 KB Output is correct
3 Execution timed out 4086 ms 11684 KB Time limit exceeded
4 Halted 0 ms 0 KB -