Submission #1119569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119569		modwwe	역사적 조사 (JOI14_historical)	C++17	100 / 100	1298 ms	17740 KiB

historic

#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 (stderr)

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]
   38 |     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]
   40 |         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]
   63 |         int a, b; scanf("%d%d", &a, &b); --a; --b;
      |                   ~~~~~^~~~~~~~~~~~~~~~

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