# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
105699 | 2019-04-14T04:14:56 Z | Pro_ktmr | 역사적 조사 (JOI14_historical) | C++14 | 1916 ms | 16776 KB |
#include <iostream> #include <iomanip> #include <fstream> #include <stdio.h> #include <math.h> #include <time.h> #include <string> #include <tuple> #include <vector> #include <map> #include <unordered_map> #include <list> #include <set> #include <stack> #include <queue> #include <cstdlib> #include <algorithm> #include <random> #include <cassert> using namespace std; #define LL long long #define MP(a, b) make_pair(a, b) #define POWER9 1000000000 #define MOD POWER9+7 #undef INT_MIN #undef INT_MAX #define INT_MIN -2147483647 #define INT_MAX 2147483647 #define LL_MIN (LL)-9223372036854775807 #define LL_MAX (LL)9223372036854775807 #define PI 3.14159265359 int N,Q; vector<int> X; vector<int> zaatu; int change[100000]; vector<int> mp[100000]; #define B 100 #define MAX_N 100000 int si; int co[100000]; LL bucket[MAX_N/B][MAX_N/B] = {};//i番目のブロックからj番目のブロックまで int main(){ scanf("%d%d", &N, &Q); for(int i=0; i<N; i++){ //N=10^5 int x; scanf("%d", &x); X.push_back(x); zaatu.push_back(x); } for(int i=N; i%B!=0; i++){ //B X.push_back(0); zaatu.push_back(0); } sort(zaatu.begin(), zaatu.end()); for(int i=0; i<N; i++){ X[i] = lower_bound(zaatu.begin(), zaatu.end(), X[i]) - zaatu.begin(); mp[X[i]].push_back(i); } si = ceil((double)N/B); for(int i=0; i<si; i++){ //N/B=10^3 LL ans = 0; for(int j=0; j<N; j++) co[j] = 0; for(int j=B*i; j<si*B; j++){ //N/B=10^3 co[X[j]]++; ans = max(ans, (LL)zaatu[X[j]]*(LL)co[X[j]]); if((j+1)%B == 0) bucket[i][(j+1)/B-1] = ans; } } for(int q=0; q<Q; q++){ //Q=10^5 int a,b; scanf("%d%d", &a, &b); a--; b--; int l = ceil((double)a/B); int r = floor((double)b/B)-1; LL ans = 0; if(l <= r) ans = bucket[l][r]; for(int i=a; i<l*B; i++){ //B=10^2 LL c = upper_bound(mp[X[i]].begin(),mp[X[i]].end(),b) - lower_bound(mp[X[i]].begin(),mp[X[i]].end(),a); ans = max(ans, (LL)zaatu[X[i]]*c); } for(int i=(r+1)*B; i<=b; i++){ //B=10^2 LL c = upper_bound(mp[X[i]].begin(),mp[X[i]].end(),b) - lower_bound(mp[X[i]].begin(),mp[X[i]].end(),a); ans = max(ans, (LL)zaatu[X[i]]*c); } cout << ans << endl; } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2688 KB | Output is correct |
2 | Correct | 4 ms | 2688 KB | Output is correct |
3 | Correct | 6 ms | 2688 KB | Output is correct |
4 | Correct | 5 ms | 2816 KB | Output is correct |
5 | Correct | 6 ms | 2688 KB | Output is correct |
6 | Correct | 6 ms | 2688 KB | Output is correct |
7 | Correct | 5 ms | 2688 KB | Output is correct |
8 | Correct | 6 ms | 2688 KB | Output is correct |
9 | Correct | 5 ms | 2688 KB | Output is correct |
10 | Correct | 5 ms | 2688 KB | Output is correct |
11 | Correct | 6 ms | 2688 KB | Output is correct |
12 | Correct | 5 ms | 2816 KB | Output is correct |
13 | Correct | 6 ms | 2688 KB | Output is correct |
14 | Correct | 7 ms | 2688 KB | Output is correct |
15 | Correct | 6 ms | 2688 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2816 KB | Output is correct |
2 | Correct | 7 ms | 2688 KB | Output is correct |
3 | Correct | 10 ms | 2816 KB | Output is correct |
4 | Correct | 19 ms | 2944 KB | Output is correct |
5 | Correct | 34 ms | 2944 KB | Output is correct |
6 | Correct | 55 ms | 3072 KB | Output is correct |
7 | Correct | 50 ms | 3072 KB | Output is correct |
8 | Correct | 53 ms | 3072 KB | Output is correct |
9 | Correct | 53 ms | 3072 KB | Output is correct |
10 | Correct | 33 ms | 3172 KB | Output is correct |
11 | Correct | 45 ms | 3320 KB | Output is correct |
12 | Correct | 48 ms | 3192 KB | Output is correct |
13 | Correct | 42 ms | 3448 KB | Output is correct |
14 | Correct | 51 ms | 3200 KB | Output is correct |
15 | Correct | 49 ms | 3200 KB | Output is correct |
16 | Correct | 59 ms | 3192 KB | Output is correct |
17 | Correct | 59 ms | 3108 KB | Output is correct |
18 | Correct | 40 ms | 3200 KB | Output is correct |
19 | Correct | 46 ms | 3320 KB | Output is correct |
20 | Correct | 35 ms | 3120 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2816 KB | Output is correct |
2 | Correct | 5 ms | 2688 KB | Output is correct |
3 | Correct | 5 ms | 2688 KB | Output is correct |
4 | Correct | 6 ms | 2816 KB | Output is correct |
5 | Correct | 11 ms | 2816 KB | Output is correct |
6 | Correct | 8 ms | 2944 KB | Output is correct |
7 | Correct | 12 ms | 3200 KB | Output is correct |
8 | Correct | 15 ms | 3712 KB | Output is correct |
9 | Correct | 36 ms | 4856 KB | Output is correct |
10 | Correct | 73 ms | 7284 KB | Output is correct |
11 | Correct | 1225 ms | 13652 KB | Output is correct |
12 | Correct | 314 ms | 12208 KB | Output is correct |
13 | Correct | 788 ms | 13040 KB | Output is correct |
14 | Correct | 1026 ms | 14060 KB | Output is correct |
15 | Correct | 1365 ms | 15928 KB | Output is correct |
16 | Correct | 534 ms | 15980 KB | Output is correct |
17 | Correct | 439 ms | 12400 KB | Output is correct |
18 | Correct | 702 ms | 13848 KB | Output is correct |
19 | Correct | 423 ms | 16776 KB | Output is correct |
20 | Correct | 263 ms | 15296 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 120 ms | 3676 KB | Output is correct |
2 | Correct | 238 ms | 4712 KB | Output is correct |
3 | Correct | 353 ms | 5712 KB | Output is correct |
4 | Correct | 412 ms | 7048 KB | Output is correct |
5 | Correct | 499 ms | 8308 KB | Output is correct |
6 | Correct | 740 ms | 9536 KB | Output is correct |
7 | Correct | 1219 ms | 10800 KB | Output is correct |
8 | Correct | 1366 ms | 12424 KB | Output is correct |
9 | Correct | 1334 ms | 13620 KB | Output is correct |
10 | Correct | 1217 ms | 14160 KB | Output is correct |
11 | Correct | 1593 ms | 14416 KB | Output is correct |
12 | Correct | 1916 ms | 14536 KB | Output is correct |
13 | Correct | 1632 ms | 14700 KB | Output is correct |
14 | Correct | 1598 ms | 15184 KB | Output is correct |
15 | Correct | 1507 ms | 15896 KB | Output is correct |
16 | Correct | 1425 ms | 15608 KB | Output is correct |
17 | Correct | 1550 ms | 15544 KB | Output is correct |
18 | Correct | 1719 ms | 15380 KB | Output is correct |
19 | Correct | 1376 ms | 15192 KB | Output is correct |
20 | Correct | 1721 ms | 15416 KB | Output is correct |
21 | Correct | 1254 ms | 15280 KB | Output is correct |
22 | Correct | 1411 ms | 15176 KB | Output is correct |
23 | Correct | 1500 ms | 14928 KB | Output is correct |
24 | Correct | 1777 ms | 15064 KB | Output is correct |
25 | Correct | 1161 ms | 14820 KB | Output is correct |