oj.uz

답안 #984184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
984184 2024-05-16T11:13:41 Z alexdd Measures (CEOI22_measures) C++17
100 / 100
 397 ms 50420 KB 
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define int long long
const int INF = 1e18;
int n,m,d;
int a[200055];
struct node
{
    int bestle,bestri;
    int rez;
    int cnt;
};
node combine(node x, node y)
{
    if(x.cnt==0)
        return y;
    if(y.cnt==0)
        return x;
    node aux;
    aux.rez = max(max(x.rez,y.rez), x.bestle + y.bestri);
    aux.cnt = x.cnt + y.cnt;
    aux.bestle = max(y.bestle, x.bestle + d*y.cnt);
    aux.bestri = max(x.bestri, y.bestri + d*x.cnt);
    return aux;
}
///max((a[i] - d*i) + (-a[j]+d*j))
node get_node(int val, int cate)
{
    node aux;
    aux.cnt = cate;
    aux.rez = d*(cate-1);
    aux.bestle = val + d*(cate-1);
    aux.bestri = -val + d*cate;
    return aux;
}
node aint[530000];
void upd(int nod, int st, int dr, int poz, node newv)
{
    if(st==dr)
    {
        aint[nod]=newv;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,newv);
    else upd(nod*2+1,mij+1,dr,poz,newv);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
map<int,int> mp,nrm;
int cntnrm;
int fr[200055];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>d;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mp[a[i]]++;
    }
    for(int pas=1;pas<=m;pas++)
    {
        cin>>a[n+pas];
        mp[a[n+pas]]++;
    }
    for(auto it:mp)
        nrm[it.first]=++cntnrm;
    for(int i=1;i<=n;i++)
    {
        fr[nrm[a[i]]]++;
        upd(1,1,cntnrm,nrm[a[i]],get_node(a[i],fr[nrm[a[i]]]));
    }
    for(int i=n+1;i<=n+m;i++)
    {
        fr[nrm[a[i]]]++;
        upd(1,1,cntnrm,nrm[a[i]],get_node(a[i],fr[nrm[a[i]]]));

        int mxm = max(0LL,aint[1].rez);
        if(mxm%2==0) cout<<mxm/2<<" ";
        else cout<<mxm/2<<".5 ";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 397 ms 47144 KB Output is correct
10 Correct 313 ms 46932 KB Output is correct
11 Correct 18 ms 7512 KB Output is correct
12 Correct 193 ms 46980 KB Output is correct
13 Correct 165 ms 46620 KB Output is correct
14 Correct 173 ms 46932 KB Output is correct
15 Correct 371 ms 46480 KB Output is correct
16 Correct 164 ms 47136 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 48148 KB Output is correct
2 Correct 178 ms 49776 KB Output is correct
3 Correct 35 ms 10324 KB Output is correct
4 Correct 173 ms 47940 KB Output is correct
5 Correct 206 ms 49208 KB Output is correct
6 Correct 179 ms 48208 KB Output is correct
7 Correct 172 ms 49236 KB Output is correct
8 Correct 181 ms 47760 KB Output is correct
9 Correct 177 ms 47740 KB Output is correct
10 Correct 176 ms 50420 KB Output is correct
11 Correct 171 ms 48732 KB Output is correct
12 Correct 175 ms 49496 KB Output is correct
13 Correct 172 ms 47700 KB Output is correct
14 Correct 182 ms 49884 KB Output is correct
15 Correct 178 ms 49488 KB Output is correct
16 Correct 168 ms 47340 KB Output is correct
17 Correct 175 ms 49056 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 48148 KB Output is correct
2 Correct 178 ms 49776 KB Output is correct
3 Correct 35 ms 10324 KB Output is correct
4 Correct 173 ms 47940 KB Output is correct
5 Correct 206 ms 49208 KB Output is correct
6 Correct 179 ms 48208 KB Output is correct
7 Correct 172 ms 49236 KB Output is correct
8 Correct 181 ms 47760 KB Output is correct
9 Correct 177 ms 47740 KB Output is correct
10 Correct 176 ms 50420 KB Output is correct
11 Correct 171 ms 48732 KB Output is correct
12 Correct 175 ms 49496 KB Output is correct
13 Correct 172 ms 47700 KB Output is correct
14 Correct 182 ms 49884 KB Output is correct
15 Correct 178 ms 49488 KB Output is correct
16 Correct 168 ms 47340 KB Output is correct
17 Correct 175 ms 49056 KB Output is correct
18 Correct 376 ms 48200 KB Output is correct
19 Correct 393 ms 49788 KB Output is correct
20 Correct 35 ms 10320 KB Output is correct
21 Correct 209 ms 48212 KB Output is correct
22 Correct 275 ms 48212 KB Output is correct
23 Correct 179 ms 47952 KB Output is correct
24 Correct 359 ms 48720 KB Output is correct
25 Correct 175 ms 47852 KB Output is correct
26 Correct 378 ms 47932 KB Output is correct
27 Correct 384 ms 50256 KB Output is correct
28 Correct 288 ms 48184 KB Output is correct
29 Correct 299 ms 49668 KB Output is correct
30 Correct 219 ms 47864 KB Output is correct
31 Correct 218 ms 49748 KB Output is correct
32 Correct 195 ms 49796 KB Output is correct
33 Correct 386 ms 47304 KB Output is correct
34 Correct 214 ms 49168 KB Output is correct