oj.uz

Submission #1049759

# Submission time Handle Problem Language Result Execution time Memory
1049759 2024-08-09T04:46:53 Z PoonYaPat Diversity (CEOI21_diversity) C++14
64 / 100
 7000 ms 240880 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int mx=300000,MID=150000,sq=1350;

struct NN {
    ll sum,sl,sr,cnt;
} s[1<<21];

NN merge(NN a, NN b) {
    NN res;
    res.sum=a.sum+b.sum;
    res.cnt=a.cnt+b.cnt;
    res.sl=a.sl+a.cnt*b.sum+b.sl;
    res.sr=b.sr+b.cnt*a.sum+a.sr;
    return res;
}

ll fast2_query(int l, int r, int idx, int x, int val) {
    if (x>r) return s[idx].sr+s[idx].sum*(ll)(x-r);
    if (x<l) return s[idx].sl+s[idx].sum*(ll)(l-x);
    if (l==r) {
        s[idx]={val,val,val,1};
        return val;
    }
    int mid=(l+r)/2;
    ll res1=fast2_query(l,mid,2*idx,x,val);
    ll res2=fast2_query(mid+1,r,2*idx+1,x,val);
    s[idx]=merge(s[2*idx],s[2*idx+1]);
    return res1+res2;
}

int have[mx+5],idx_seq=-1;
vector<int> seq;
deque<int> dq[mx+5];
ll ans=0;

void add(int val) {

    if (!have[val]) {
        int pos=seq[++idx_seq];
        dq[1].push_back(pos);
        ans+=fast2_query(1,mx,1,pos,1);

    } else {
        int max_pos=dq[have[val]].front();
        dq[have[val]].pop_front();
        dq[have[val]+1].push_back(max_pos);
        ans+=fast2_query(1,mx,1,max_pos,have[val]+1);
    }

    ++have[val];
}

void del(int val) {

    int min_pos=dq[have[val]].back();
    dq[have[val]].pop_back();

    if (have[val]==1) --idx_seq;
    else dq[have[val]-1].push_front(min_pos);

    --have[val];
    ans-=(fast2_query(1,mx,1,min_pos,have[val])+1);
}

int n,q,a[mx+5];

struct Query {
    int l,r,idx;
    bool operator<(Query other) const {
        return pii(l/sq,((l/sq)&1) ? -r : +r)<pii(other.l/sq,((other.l/sq)&1) ? -other.r : +other.r);
    }
};

vector<Query> ques;
ll Ans[50005];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ll=MID,rr=MID;
    seq.push_back(MID);
    for (int i=1; i<mx; ++i) {
        if (i%2==0) seq.push_back(--ll);
        else seq.push_back(++rr);
    }

    cin>>n>>q;
    for (int i=0; i<n; ++i) cin>>a[i];

    for (int i=0; i<q; ++i) {
        int l,r; cin>>l>>r;
        ques.push_back({--l,--r,i});
    }

    sort(ques.begin(),ques.end());

    int cur_l=0;
    int cur_r=-1;

    for (auto q : ques) {
        if (q.l>cur_r) {
            for (int i=q.l; i<=q.r; ++i) add(a[i]);
            for (int i=cur_l; i<=cur_r; ++i) del(a[i]);
            cur_l=q.l; cur_r=q.r;
        } else if (q.r<cur_l) {
            for (int i=q.l; i<=q.r; ++i) add(a[i]);
            for (int i=cur_l; i<=cur_r; ++i) del(a[i]);
            cur_l=q.l; cur_r=q.r;
        } else {
            while (cur_l>q.l) add(a[--cur_l]);
            while (cur_r<q.r) add(a[++cur_r]);
            while (cur_l<q.l) del(a[cur_l++]);
            while (cur_r>q.r) del(a[cur_r--]);
        }
        Ans[q.idx]=ans;
    }

    for (int i=0; i<q; ++i) cout<<Ans[i]<<"\n";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 207560 KB Output is correct
2 Correct 72 ms 208836 KB Output is correct
3 Correct 74 ms 208984 KB Output is correct
4 Correct 79 ms 208832 KB Output is correct
5 Correct 68 ms 208876 KB Output is correct
6 Correct 72 ms 208836 KB Output is correct
7 Correct 67 ms 208832 KB Output is correct
8 Correct 73 ms 208752 KB Output is correct
9 Correct 68 ms 208832 KB Output is correct
10 Correct 68 ms 208960 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 208836 KB Output is correct
2 Correct 81 ms 208836 KB Output is correct
3 Correct 74 ms 208848 KB Output is correct
4 Correct 103 ms 208964 KB Output is correct
5 Correct 107 ms 209228 KB Output is correct
6 Correct 130 ms 209584 KB Output is correct
7 Correct 128 ms 209348 KB Output is correct
8 Correct 130 ms 209508 KB Output is correct
9 Correct 135 ms 209600 KB Output is correct
10 Correct 137 ms 209608 KB Output is correct
11 Correct 143 ms 209604 KB Output is correct
12 Correct 146 ms 209452 KB Output is correct
13 Correct 129 ms 209856 KB Output is correct
14 Correct 130 ms 209604 KB Output is correct
15 Correct 131 ms 209600 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 208836 KB Output is correct
2 Correct 81 ms 208836 KB Output is correct
3 Correct 74 ms 208848 KB Output is correct
4 Correct 103 ms 208964 KB Output is correct
5 Correct 107 ms 209228 KB Output is correct
6 Correct 130 ms 209584 KB Output is correct
7 Correct 128 ms 209348 KB Output is correct
8 Correct 130 ms 209508 KB Output is correct
9 Correct 135 ms 209600 KB Output is correct
10 Correct 137 ms 209608 KB Output is correct
11 Correct 143 ms 209604 KB Output is correct
12 Correct 146 ms 209452 KB Output is correct
13 Correct 129 ms 209856 KB Output is correct
14 Correct 130 ms 209604 KB Output is correct
15 Correct 131 ms 209600 KB Output is correct
16 Correct 71 ms 208836 KB Output is correct
17 Correct 75 ms 208960 KB Output is correct
18 Correct 75 ms 208832 KB Output is correct
19 Correct 96 ms 209088 KB Output is correct
20 Correct 112 ms 209348 KB Output is correct
21 Correct 135 ms 209716 KB Output is correct
22 Correct 125 ms 209660 KB Output is correct
23 Correct 125 ms 209600 KB Output is correct
24 Correct 128 ms 209568 KB Output is correct
25 Correct 123 ms 209740 KB Output is correct
26 Correct 127 ms 209540 KB Output is correct
27 Correct 126 ms 209604 KB Output is correct
28 Correct 122 ms 209600 KB Output is correct
29 Correct 131 ms 209628 KB Output is correct
30 Correct 128 ms 209604 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 208836 KB Output is correct
2 Correct 81 ms 208836 KB Output is correct
3 Correct 74 ms 208848 KB Output is correct
4 Correct 103 ms 208964 KB Output is correct
5 Correct 107 ms 209228 KB Output is correct
6 Correct 130 ms 209584 KB Output is correct
7 Correct 128 ms 209348 KB Output is correct
8 Correct 130 ms 209508 KB Output is correct
9 Correct 135 ms 209600 KB Output is correct
10 Correct 137 ms 209608 KB Output is correct
11 Correct 143 ms 209604 KB Output is correct
12 Correct 146 ms 209452 KB Output is correct
13 Correct 129 ms 209856 KB Output is correct
14 Correct 130 ms 209604 KB Output is correct
15 Correct 131 ms 209600 KB Output is correct
16 Correct 71 ms 208836 KB Output is correct
17 Correct 75 ms 208960 KB Output is correct
18 Correct 75 ms 208832 KB Output is correct
19 Correct 96 ms 209088 KB Output is correct
20 Correct 112 ms 209348 KB Output is correct
21 Correct 135 ms 209716 KB Output is correct
22 Correct 125 ms 209660 KB Output is correct
23 Correct 125 ms 209600 KB Output is correct
24 Correct 128 ms 209568 KB Output is correct
25 Correct 123 ms 209740 KB Output is correct
26 Correct 127 ms 209540 KB Output is correct
27 Correct 126 ms 209604 KB Output is correct
28 Correct 122 ms 209600 KB Output is correct
29 Correct 131 ms 209628 KB Output is correct
30 Correct 128 ms 209604 KB Output is correct
31 Correct 68 ms 208832 KB Output is correct
32 Correct 67 ms 208832 KB Output is correct
33 Correct 66 ms 208756 KB Output is correct
34 Correct 73 ms 208836 KB Output is correct
35 Correct 71 ms 208832 KB Output is correct
36 Correct 82 ms 208832 KB Output is correct
37 Correct 86 ms 209092 KB Output is correct
38 Correct 86 ms 209144 KB Output is correct
39 Correct 109 ms 209344 KB Output is correct
40 Correct 118 ms 209584 KB Output is correct
41 Correct 134 ms 210108 KB Output is correct
42 Correct 135 ms 210092 KB Output is correct
43 Correct 139 ms 210116 KB Output is correct
44 Correct 132 ms 209964 KB Output is correct
45 Correct 133 ms 210116 KB Output is correct
46 Correct 131 ms 210116 KB Output is correct
47 Correct 158 ms 210112 KB Output is correct
48 Correct 137 ms 210144 KB Output is correct
49 Correct 132 ms 210112 KB Output is correct
50 Correct 136 ms 209932 KB Output is correct
51 Correct 133 ms 210112 KB Output is correct
52 Correct 141 ms 210112 KB Output is correct
53 Correct 137 ms 210116 KB Output is correct
54 Correct 123 ms 210112 KB Output is correct
55 Correct 131 ms 209952 KB Output is correct
56 Correct 136 ms 210116 KB Output is correct
57 Correct 124 ms 210112 KB Output is correct
58 Correct 136 ms 209944 KB Output is correct
59 Correct 136 ms 209960 KB Output is correct
60 Correct 134 ms 210176 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 207560 KB Output is correct
2 Correct 72 ms 208836 KB Output is correct
3 Correct 74 ms 208984 KB Output is correct
4 Correct 79 ms 208832 KB Output is correct
5 Correct 68 ms 208876 KB Output is correct
6 Correct 72 ms 208836 KB Output is correct
7 Correct 67 ms 208832 KB Output is correct
8 Correct 73 ms 208752 KB Output is correct
9 Correct 68 ms 208832 KB Output is correct
10 Correct 68 ms 208960 KB Output is correct
11 Correct 70 ms 208836 KB Output is correct
12 Correct 81 ms 208836 KB Output is correct
13 Correct 74 ms 208848 KB Output is correct
14 Correct 103 ms 208964 KB Output is correct
15 Correct 107 ms 209228 KB Output is correct
16 Correct 130 ms 209584 KB Output is correct
17 Correct 128 ms 209348 KB Output is correct
18 Correct 130 ms 209508 KB Output is correct
19 Correct 135 ms 209600 KB Output is correct
20 Correct 137 ms 209608 KB Output is correct
21 Correct 143 ms 209604 KB Output is correct
22 Correct 146 ms 209452 KB Output is correct
23 Correct 129 ms 209856 KB Output is correct
24 Correct 130 ms 209604 KB Output is correct
25 Correct 131 ms 209600 KB Output is correct
26 Correct 71 ms 208836 KB Output is correct
27 Correct 75 ms 208960 KB Output is correct
28 Correct 75 ms 208832 KB Output is correct
29 Correct 96 ms 209088 KB Output is correct
30 Correct 112 ms 209348 KB Output is correct
31 Correct 135 ms 209716 KB Output is correct
32 Correct 125 ms 209660 KB Output is correct
33 Correct 125 ms 209600 KB Output is correct
34 Correct 128 ms 209568 KB Output is correct
35 Correct 123 ms 209740 KB Output is correct
36 Correct 127 ms 209540 KB Output is correct
37 Correct 126 ms 209604 KB Output is correct
38 Correct 122 ms 209600 KB Output is correct
39 Correct 131 ms 209628 KB Output is correct
40 Correct 128 ms 209604 KB Output is correct
41 Correct 68 ms 208832 KB Output is correct
42 Correct 67 ms 208832 KB Output is correct
43 Correct 66 ms 208756 KB Output is correct
44 Correct 73 ms 208836 KB Output is correct
45 Correct 71 ms 208832 KB Output is correct
46 Correct 82 ms 208832 KB Output is correct
47 Correct 86 ms 209092 KB Output is correct
48 Correct 86 ms 209144 KB Output is correct
49 Correct 109 ms 209344 KB Output is correct
50 Correct 118 ms 209584 KB Output is correct
51 Correct 134 ms 210108 KB Output is correct
52 Correct 135 ms 210092 KB Output is correct
53 Correct 139 ms 210116 KB Output is correct
54 Correct 132 ms 209964 KB Output is correct
55 Correct 133 ms 210116 KB Output is correct
56 Correct 131 ms 210116 KB Output is correct
57 Correct 158 ms 210112 KB Output is correct
58 Correct 137 ms 210144 KB Output is correct
59 Correct 132 ms 210112 KB Output is correct
60 Correct 136 ms 209932 KB Output is correct
61 Correct 133 ms 210112 KB Output is correct
62 Correct 141 ms 210112 KB Output is correct
63 Correct 137 ms 210116 KB Output is correct
64 Correct 123 ms 210112 KB Output is correct
65 Correct 131 ms 209952 KB Output is correct
66 Correct 136 ms 210116 KB Output is correct
67 Correct 124 ms 210112 KB Output is correct
68 Correct 136 ms 209944 KB Output is correct
69 Correct 136 ms 209960 KB Output is correct
70 Correct 134 ms 210176 KB Output is correct
71 Correct 85 ms 209268 KB Output is correct
72 Correct 95 ms 209204 KB Output is correct
73 Correct 84 ms 209108 KB Output is correct
74 Correct 90 ms 209092 KB Output is correct
75 Correct 90 ms 209092 KB Output is correct
76 Correct 100 ms 209604 KB Output is correct
77 Correct 100 ms 209604 KB Output is correct
78 Correct 97 ms 209604 KB Output is correct
79 Correct 99 ms 209600 KB Output is correct
80 Correct 96 ms 209496 KB Output is correct
81 Correct 113 ms 210364 KB Output is correct
82 Correct 116 ms 210304 KB Output is correct
83 Correct 122 ms 210368 KB Output is correct
84 Correct 116 ms 210448 KB Output is correct
85 Correct 117 ms 210460 KB Output is correct
86 Correct 110 ms 210884 KB Output is correct
87 Correct 105 ms 210876 KB Output is correct
88 Correct 109 ms 210880 KB Output is correct
89 Correct 109 ms 210984 KB Output is correct
90 Correct 128 ms 211136 KB Output is correct
91 Correct 156 ms 224956 KB Output is correct
92 Correct 144 ms 224936 KB Output is correct
93 Correct 141 ms 224972 KB Output is correct
94 Correct 148 ms 224960 KB Output is correct
95 Correct 138 ms 224940 KB Output is correct
96 Correct 148 ms 235456 KB Output is correct
97 Correct 141 ms 235492 KB Output is correct
98 Correct 154 ms 235564 KB Output is correct
99 Correct 142 ms 235452 KB Output is correct
100 Correct 146 ms 235456 KB Output is correct
101 Correct 148 ms 235572 KB Output is correct
102 Correct 142 ms 235712 KB Output is correct
103 Correct 143 ms 235516 KB Output is correct
104 Correct 148 ms 235432 KB Output is correct
105 Correct 148 ms 235568 KB Output is correct
106 Correct 147 ms 240832 KB Output is correct
107 Correct 137 ms 240832 KB Output is correct
108 Correct 140 ms 240828 KB Output is correct
109 Correct 145 ms 240732 KB Output is correct
110 Correct 147 ms 240880 KB Output is correct
111 Correct 156 ms 240740 KB Output is correct
112 Correct 144 ms 240788 KB Output is correct
113 Correct 140 ms 240828 KB Output is correct
114 Correct 143 ms 240832 KB Output is correct
115 Correct 140 ms 240736 KB Output is correct

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 207560 KB Output is correct
2 Correct 72 ms 208836 KB Output is correct
3 Correct 74 ms 208984 KB Output is correct
4 Correct 79 ms 208832 KB Output is correct
5 Correct 68 ms 208876 KB Output is correct
6 Correct 72 ms 208836 KB Output is correct
7 Correct 67 ms 208832 KB Output is correct
8 Correct 73 ms 208752 KB Output is correct
9 Correct 68 ms 208832 KB Output is correct
10 Correct 68 ms 208960 KB Output is correct
11 Correct 70 ms 208836 KB Output is correct
12 Correct 81 ms 208836 KB Output is correct
13 Correct 74 ms 208848 KB Output is correct
14 Correct 103 ms 208964 KB Output is correct
15 Correct 107 ms 209228 KB Output is correct
16 Correct 130 ms 209584 KB Output is correct
17 Correct 128 ms 209348 KB Output is correct
18 Correct 130 ms 209508 KB Output is correct
19 Correct 135 ms 209600 KB Output is correct
20 Correct 137 ms 209608 KB Output is correct
21 Correct 143 ms 209604 KB Output is correct
22 Correct 146 ms 209452 KB Output is correct
23 Correct 129 ms 209856 KB Output is correct
24 Correct 130 ms 209604 KB Output is correct
25 Correct 131 ms 209600 KB Output is correct
26 Correct 71 ms 208836 KB Output is correct
27 Correct 75 ms 208960 KB Output is correct
28 Correct 75 ms 208832 KB Output is correct
29 Correct 96 ms 209088 KB Output is correct
30 Correct 112 ms 209348 KB Output is correct
31 Correct 135 ms 209716 KB Output is correct
32 Correct 125 ms 209660 KB Output is correct
33 Correct 125 ms 209600 KB Output is correct
34 Correct 128 ms 209568 KB Output is correct
35 Correct 123 ms 209740 KB Output is correct
36 Correct 127 ms 209540 KB Output is correct
37 Correct 126 ms 209604 KB Output is correct
38 Correct 122 ms 209600 KB Output is correct
39 Correct 131 ms 209628 KB Output is correct
40 Correct 128 ms 209604 KB Output is correct
41 Correct 68 ms 208832 KB Output is correct
42 Correct 67 ms 208832 KB Output is correct
43 Correct 66 ms 208756 KB Output is correct
44 Correct 73 ms 208836 KB Output is correct
45 Correct 71 ms 208832 KB Output is correct
46 Correct 82 ms 208832 KB Output is correct
47 Correct 86 ms 209092 KB Output is correct
48 Correct 86 ms 209144 KB Output is correct
49 Correct 109 ms 209344 KB Output is correct
50 Correct 118 ms 209584 KB Output is correct
51 Correct 134 ms 210108 KB Output is correct
52 Correct 135 ms 210092 KB Output is correct
53 Correct 139 ms 210116 KB Output is correct
54 Correct 132 ms 209964 KB Output is correct
55 Correct 133 ms 210116 KB Output is correct
56 Correct 131 ms 210116 KB Output is correct
57 Correct 158 ms 210112 KB Output is correct
58 Correct 137 ms 210144 KB Output is correct
59 Correct 132 ms 210112 KB Output is correct
60 Correct 136 ms 209932 KB Output is correct
61 Correct 133 ms 210112 KB Output is correct
62 Correct 141 ms 210112 KB Output is correct
63 Correct 137 ms 210116 KB Output is correct
64 Correct 123 ms 210112 KB Output is correct
65 Correct 131 ms 209952 KB Output is correct
66 Correct 136 ms 210116 KB Output is correct
67 Correct 124 ms 210112 KB Output is correct
68 Correct 136 ms 209944 KB Output is correct
69 Correct 136 ms 209960 KB Output is correct
70 Correct 134 ms 210176 KB Output is correct
71 Correct 85 ms 209268 KB Output is correct
72 Correct 95 ms 209204 KB Output is correct
73 Correct 84 ms 209108 KB Output is correct
74 Correct 90 ms 209092 KB Output is correct
75 Correct 90 ms 209092 KB Output is correct
76 Correct 100 ms 209604 KB Output is correct
77 Correct 100 ms 209604 KB Output is correct
78 Correct 97 ms 209604 KB Output is correct
79 Correct 99 ms 209600 KB Output is correct
80 Correct 96 ms 209496 KB Output is correct
81 Correct 113 ms 210364 KB Output is correct
82 Correct 116 ms 210304 KB Output is correct
83 Correct 122 ms 210368 KB Output is correct
84 Correct 116 ms 210448 KB Output is correct
85 Correct 117 ms 210460 KB Output is correct
86 Correct 110 ms 210884 KB Output is correct
87 Correct 105 ms 210876 KB Output is correct
88 Correct 109 ms 210880 KB Output is correct
89 Correct 109 ms 210984 KB Output is correct
90 Correct 128 ms 211136 KB Output is correct
91 Correct 156 ms 224956 KB Output is correct
92 Correct 144 ms 224936 KB Output is correct
93 Correct 141 ms 224972 KB Output is correct
94 Correct 148 ms 224960 KB Output is correct
95 Correct 138 ms 224940 KB Output is correct
96 Correct 148 ms 235456 KB Output is correct
97 Correct 141 ms 235492 KB Output is correct
98 Correct 154 ms 235564 KB Output is correct
99 Correct 142 ms 235452 KB Output is correct
100 Correct 146 ms 235456 KB Output is correct
101 Correct 148 ms 235572 KB Output is correct
102 Correct 142 ms 235712 KB Output is correct
103 Correct 143 ms 235516 KB Output is correct
104 Correct 148 ms 235432 KB Output is correct
105 Correct 148 ms 235568 KB Output is correct
106 Correct 147 ms 240832 KB Output is correct
107 Correct 137 ms 240832 KB Output is correct
108 Correct 140 ms 240828 KB Output is correct
109 Correct 145 ms 240732 KB Output is correct
110 Correct 147 ms 240880 KB Output is correct
111 Correct 156 ms 240740 KB Output is correct
112 Correct 144 ms 240788 KB Output is correct
113 Correct 140 ms 240828 KB Output is correct
114 Correct 143 ms 240832 KB Output is correct
115 Correct 140 ms 240736 KB Output is correct
116 Correct 2926 ms 211168 KB Output is correct
117 Correct 3036 ms 211168 KB Output is correct
118 Correct 3248 ms 211624 KB Output is correct
119 Correct 3334 ms 211648 KB Output is correct
120 Correct 3402 ms 211644 KB Output is correct
121 Correct 3819 ms 211904 KB Output is correct
122 Correct 3976 ms 212028 KB Output is correct
123 Correct 5682 ms 212356 KB Output is correct
124 Correct 5733 ms 212744 KB Output is correct
125 Correct 5715 ms 213184 KB Output is correct
126 Execution timed out 7039 ms 211904 KB Time limit exceeded
127 Halted 0 ms 0 KB -