oj.uz

Submission #259019

# Submission time Handle Problem Language Result Execution time Memory
259019 2020-08-07T04:21:49 Z admin 역사적 조사 (JOI14_historical) C++14
100 / 100
 1618 ms 18040 KB 
#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h> 
#include <time.h>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
 
const int N_ = 150005;
const int B = 110;
int N, Q, X[N_], S[N_], SN, P[N_];
vector<int> W[N_];
ll precalc[N_/B][N_/B], C[N_];
 
int main() {
    scanf("%d%d", &N, &Q);
    for(int i = 0; i < N; i++) {
        scanf("%d", X+i);
        S[i] = X[i];
    }
 
    sort(S, S+N);
    SN = unique(S, S+N) - S;
     
    for(int i = 0; i < N; i++) {
        P[i] = lower_bound(S, S+SN, X[i]) - S;
        W[P[i]].push_back(i);
    }
 
    for(int i = 0; i < N; i += B) {
        for(int j = 0; j < N; j++) C[j] = 0;
        ll val = 0;
        for(int j = i; j < N; j++) {
            C[P[j]] += (ll)X[j];
            if(val < C[P[j]]) val = C[P[j]];
            if(j % B == 0) precalc[i/B][j/B] = val;
        }
    }
 
    while(Q--) {
        int a, b; scanf("%d%d", &a, &b); --a; --b;
        int x = a, y = b;
        ll ans = 0;
        for(; x % B != 0; ++x) {
            ll val = (ll)X[x] * (lower_bound(W[P[x]].begin(), W[P[x]].end(), b+1) - lower_bound(W[P[x]].begin(), W[P[x]].end(), a));
            if(val > ans) ans = val;
        }
        for(; y % B != 0; --y) {
            ll val = (ll)X[y] * (lower_bound(W[P[y]].begin(), W[P[y]].end(), b+1) - lower_bound(W[P[y]].begin(), W[P[y]].end(), a));
            if(val > ans) ans = val;
        }
        ans = max(ans, precalc[x/B][y/B]);
 
        printf("%lld\n", ans);
    }
 
    return 0;
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
historic.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", X+i);
         ~~~~~^~~~~~~~~~~
historic.cpp:63:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d%d", &a, &b); --a; --b;
                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3840 KB Output is correct
2 Correct 4 ms 3840 KB Output is correct
3 Correct 7 ms 3968 KB Output is correct
4 Correct 13 ms 3968 KB Output is correct
5 Correct 27 ms 4096 KB Output is correct
6 Correct 49 ms 4224 KB Output is correct
7 Correct 43 ms 4224 KB Output is correct
8 Correct 52 ms 4224 KB Output is correct
9 Correct 52 ms 4236 KB Output is correct
10 Correct 25 ms 4224 KB Output is correct
11 Correct 27 ms 4224 KB Output is correct
12 Correct 29 ms 4224 KB Output is correct
13 Correct 34 ms 4224 KB Output is correct
14 Correct 32 ms 4224 KB Output is correct
15 Correct 30 ms 4224 KB Output is correct
16 Correct 56 ms 4224 KB Output is correct
17 Correct 45 ms 4224 KB Output is correct
18 Correct 32 ms 4224 KB Output is correct
19 Correct 25 ms 4224 KB Output is correct
20 Correct 31 ms 4224 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3840 KB Output is correct
2 Correct 3 ms 3840 KB Output is correct
3 Correct 3 ms 3840 KB Output is correct
4 Correct 4 ms 3840 KB Output is correct
5 Correct 6 ms 3968 KB Output is correct
6 Correct 6 ms 4096 KB Output is correct
7 Correct 6 ms 4224 KB Output is correct
8 Correct 11 ms 4736 KB Output is correct
9 Correct 29 ms 5760 KB Output is correct
10 Correct 68 ms 7924 KB Output is correct
11 Correct 1213 ms 14004 KB Output is correct
12 Correct 231 ms 13176 KB Output is correct
13 Correct 401 ms 13604 KB Output is correct
14 Correct 497 ms 14584 KB Output is correct
15 Correct 622 ms 15608 KB Output is correct
16 Correct 349 ms 16308 KB Output is correct
17 Correct 426 ms 13560 KB Output is correct
18 Correct 761 ms 14200 KB Output is correct
19 Correct 321 ms 16632 KB Output is correct
20 Correct 264 ms 15968 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 4608 KB Output is correct
2 Correct 197 ms 5404 KB Output is correct
3 Correct 245 ms 6260 KB Output is correct
4 Correct 274 ms 7544 KB Output is correct
5 Correct 402 ms 8456 KB Output is correct
6 Correct 594 ms 10872 KB Output is correct
7 Correct 973 ms 12028 KB Output is correct
8 Correct 1242 ms 14072 KB Output is correct
9 Correct 1284 ms 15480 KB Output is correct
10 Correct 985 ms 16112 KB Output is correct
11 Correct 1474 ms 16528 KB Output is correct
12 Correct 1618 ms 16504 KB Output is correct
13 Correct 1142 ms 16504 KB Output is correct
14 Correct 796 ms 17272 KB Output is correct
15 Correct 714 ms 18040 KB Output is correct
16 Correct 754 ms 17528 KB Output is correct
17 Correct 765 ms 17400 KB Output is correct
18 Correct 800 ms 17200 KB Output is correct
19 Correct 811 ms 17228 KB Output is correct
20 Correct 829 ms 17016 KB Output is correct
21 Correct 882 ms 17272 KB Output is correct
22 Correct 853 ms 17272 KB Output is correct
23 Correct 865 ms 17116 KB Output is correct
24 Correct 886 ms 17272 KB Output is correct
25 Correct 974 ms 16880 KB Output is correct