oj.uz

Submission #486039

# Submission time Handle Problem Language Result Execution time Memory
486039 2021-11-10T12:10:14 Z urd05 역사적 조사 (JOI14_historical) C++17
100 / 100
 3630 ms 15284 KB 
#include <bits/stdc++.h>
using namespace std;
 
vector<int> press;
vector<int> vec[100000];
int n,q;
int arr[100000];
const int sq=320;
int save[320][320];
typedef pair<long long,int> P;
bool chk[100000];
 
long long cal(int x,int l,int r) {
    return press[x]*(upper_bound(vec[x].begin(),vec[x].end(),r)-lower_bound(vec[x].begin(),vec[x].end(),l));
}
 
int main(void) {
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++) {
        scanf("%d",&arr[i]);
        press.push_back(arr[i]);
    }
    sort(press.begin(),press.end());
    press.erase(unique(press.begin(),press.end()),press.end());
    for(int i=0;i<n;i++) {
        arr[i]=lower_bound(press.begin(),press.end(),arr[i])-press.begin();
        vec[arr[i]].push_back(i);
    }
    for(int i=0;i<n;i+=sq) {
        priority_queue<P> pq;
        priority_queue<P> er;
        vector<long long> temp(press.size());
        for(int j=0;j<press.size();j++) {
            pq.push(P(0,j));
            temp[j]=0;
        }
        for(int j=i;j<n;j++) {
            er.push(P(temp[arr[j]],arr[j]));
            temp[arr[j]]+=press[arr[j]];
            pq.push(P(temp[arr[j]],arr[j]));
            while (!er.empty()&&pq.top()==er.top()) {
                pq.pop();
                er.pop();
            }
            if (j%sq==sq-1) {
                save[i/sq][j/sq]=pq.top().second;
            }
        }
    }
    for(int i=0;i<q;i++) {
        int l,r;
        scanf("%d %d",&l,&r);
        l--;
        r--;
        int ll=l;
        int rr=r;
        vector<int> hubo;
        if (l/sq==r/sq) {
            for(int j=l;j<=r;j++) {
                if (!chk[arr[j]])
                hubo.push_back(arr[j]);
                chk[arr[j]]=true;
            }
        }
        else {
            while (l%sq!=0) {
                if (!chk[arr[l]])
                hubo.push_back(arr[l]);
                chk[arr[l]]=true;
                l++;
            }
            while (r%sq!=sq-1) {
                if (!chk[arr[r]])
                hubo.push_back(arr[r]);
                chk[arr[r]]=true;
                r--;
            }
            if (l/sq<=r/sq)
                hubo.push_back(save[l/sq][r/sq]);
        }
        long long ret=0;
        for(int j=0;j<hubo.size();j++) {
            ret=max(ret,cal(hubo[j],ll,rr));
            chk[hubo[j]]=false;
        }
        printf("%lld\n",ret);
    }
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int j=0;j<press.size();j++) {
      |                     ~^~~~~~~~~~~~~
historic.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int j=0;j<hubo.size();j++) {
      |                     ~^~~~~~~~~~~~
historic.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
historic.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%d",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~
historic.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d %d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 1 ms 2636 KB Output is correct
16 Correct 2 ms 2672 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 8 ms 2636 KB Output is correct
19 Correct 14 ms 2764 KB Output is correct
20 Correct 32 ms 2892 KB Output is correct
21 Correct 44 ms 3036 KB Output is correct
22 Correct 54 ms 3004 KB Output is correct
23 Correct 27 ms 2996 KB Output is correct
24 Correct 29 ms 3020 KB Output is correct
25 Correct 59 ms 3156 KB Output is correct
26 Correct 68 ms 3088 KB Output is correct
27 Correct 71 ms 3052 KB Output is correct
28 Correct 65 ms 3052 KB Output is correct
29 Correct 79 ms 3036 KB Output is correct
30 Correct 76 ms 3044 KB Output is correct
31 Correct 40 ms 3068 KB Output is correct
32 Correct 17 ms 3020 KB Output is correct
33 Correct 71 ms 3080 KB Output is correct
34 Correct 61 ms 3136 KB Output is correct
35 Correct 61 ms 3068 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 11 ms 3128 KB Output is correct
8 Correct 34 ms 3728 KB Output is correct
9 Correct 104 ms 4864 KB Output is correct
10 Correct 324 ms 6252 KB Output is correct
11 Correct 1272 ms 9848 KB Output is correct
12 Correct 1066 ms 9956 KB Output is correct
13 Correct 1602 ms 10424 KB Output is correct
14 Correct 2090 ms 13016 KB Output is correct
15 Correct 2091 ms 13992 KB Output is correct
16 Correct 3297 ms 14588 KB Output is correct
17 Correct 1439 ms 9160 KB Output is correct
18 Correct 1551 ms 9028 KB Output is correct
19 Correct 3630 ms 14580 KB Output is correct
20 Correct 3337 ms 14604 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 1 ms 2636 KB Output is correct
16 Correct 2 ms 2672 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 8 ms 2636 KB Output is correct
19 Correct 14 ms 2764 KB Output is correct
20 Correct 32 ms 2892 KB Output is correct
21 Correct 44 ms 3036 KB Output is correct
22 Correct 54 ms 3004 KB Output is correct
23 Correct 27 ms 2996 KB Output is correct
24 Correct 29 ms 3020 KB Output is correct
25 Correct 59 ms 3156 KB Output is correct
26 Correct 68 ms 3088 KB Output is correct
27 Correct 71 ms 3052 KB Output is correct
28 Correct 65 ms 3052 KB Output is correct
29 Correct 79 ms 3036 KB Output is correct
30 Correct 76 ms 3044 KB Output is correct
31 Correct 40 ms 3068 KB Output is correct
32 Correct 17 ms 3020 KB Output is correct
33 Correct 71 ms 3080 KB Output is correct
34 Correct 61 ms 3136 KB Output is correct
35 Correct 61 ms 3068 KB Output is correct
36 Correct 2 ms 2636 KB Output is correct
37 Correct 2 ms 2636 KB Output is correct
38 Correct 2 ms 2636 KB Output is correct
39 Correct 2 ms 2636 KB Output is correct
40 Correct 4 ms 2764 KB Output is correct
41 Correct 4 ms 2892 KB Output is correct
42 Correct 11 ms 3128 KB Output is correct
43 Correct 34 ms 3728 KB Output is correct
44 Correct 104 ms 4864 KB Output is correct
45 Correct 324 ms 6252 KB Output is correct
46 Correct 1272 ms 9848 KB Output is correct
47 Correct 1066 ms 9956 KB Output is correct
48 Correct 1602 ms 10424 KB Output is correct
49 Correct 2090 ms 13016 KB Output is correct
50 Correct 2091 ms 13992 KB Output is correct
51 Correct 3297 ms 14588 KB Output is correct
52 Correct 1439 ms 9160 KB Output is correct
53 Correct 1551 ms 9028 KB Output is correct
54 Correct 3630 ms 14580 KB Output is correct
55 Correct 3337 ms 14604 KB Output is correct
56 Correct 111 ms 3392 KB Output is correct
57 Correct 394 ms 4196 KB Output is correct
58 Correct 598 ms 5488 KB Output is correct
59 Correct 876 ms 6508 KB Output is correct
60 Correct 1014 ms 7796 KB Output is correct
61 Correct 1561 ms 6424 KB Output is correct
62 Correct 1749 ms 8344 KB Output is correct
63 Correct 1194 ms 9020 KB Output is correct
64 Correct 1179 ms 8944 KB Output is correct
65 Correct 1727 ms 9704 KB Output is correct
66 Correct 1519 ms 9924 KB Output is correct
67 Correct 2714 ms 9920 KB Output is correct
68 Correct 3215 ms 10276 KB Output is correct
69 Correct 2763 ms 15284 KB Output is correct
70 Correct 3111 ms 15036 KB Output is correct
71 Correct 2890 ms 14280 KB Output is correct
72 Correct 2820 ms 14276 KB Output is correct
73 Correct 2816 ms 14212 KB Output is correct
74 Correct 2882 ms 14152 KB Output is correct
75 Correct 3194 ms 12572 KB Output is correct
76 Correct 3227 ms 12588 KB Output is correct
77 Correct 3159 ms 12432 KB Output is correct
78 Correct 3168 ms 12400 KB Output is correct
79 Correct 3153 ms 12328 KB Output is correct
80 Correct 1596 ms 11296 KB Output is correct