Submission #1099751

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1099751	2024-10-12T05:10:12 Z	model_code	Nile (IOI24_nile)	C++17	100 / 100	91 ms	16260 KB

nile

// model_solution/badawy_solution.cpp

#include <bits/stdc++.h>

using namespace std ;

const int N = 1e5 + 10 ;
int n,q;
array<int, 3> arr[N];
int uni[N], sz[N], l[N], r[N], mn[N], mnp[N][2];
long long sum[N];
long long ans;

int uni_find(int x)
{
    return uni[x]=(uni[x]==x?x:uni_find(uni[x]));
}

long long calc(int x)
{
    int a=l[x];
    return sum[x] + (sz[x]%2 ? min({mn[x], mnp[x][a&1]}) : 0);
}

void unio(int x,int y)
{
    x=uni_find(x); y=uni_find(y);
    if(x==y) return;
    ans-=calc(x);
    ans-=calc(y);
    sz[x]+=sz[y];
    l[x]=min(l[x], l[y]);
    r[x]=max(r[x], r[y]);
    mn[x]=min({mn[x], mn[y]});
    mnp[x][0]=min(mnp[x][0], mnp[y][0]);
    mnp[x][1]=min(mnp[x][1], mnp[y][1]);
    sum[x]+=sum[y];
    uni[y]=x;
    ans+=calc(x);
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
	n=W.size(); q=E.size();
    for(int i=0;i<n;i++)
    {
        arr[i]={W[i], A[i], B[i]};
    }
    sort(arr,arr+n);
    for(int i=0;i<n;i++)
    {
        uni[i]=l[i]=r[i]=i;
        sz[i]=1;
        mn[i]=(1<<30);
        sum[i]=arr[i][2]-arr[i][1];
        mnp[i][0]=mnp[i][1]=(1<<30);
        mnp[i][i&1] = -sum[i];
        ans+=A[i];
    }
    vector<array<int, 3> > eds;
    for(int i=0;i<n-1;i++)
    {
        eds.push_back({arr[i+1][0]-arr[i][0], -2, i});
        if(i+2<n)
            eds.push_back({arr[i+2][0]-arr[i][0], -1, i});
    }
    for(int i=0;i<q;i++)
        eds.push_back({E[i], 0, i});
    sort(eds.begin(), eds.end());
    vector<long long> ret(q);
    for(auto ed:eds) {
        if(ed[1]==0) ret[ed[2]]=ans;
        else if(ed[1]==-2) {
            unio(ed[2], ed[2]+1);
        }
        else {
            int x=uni_find(ed[2]), y=uni_find(ed[2]+2);
            assert(x==y);
            ans-=calc(x);
            int cost=arr[ed[2]+1][1] - arr[ed[2]+1][2];
            mn[x]=min(mn[x], cost);
            ans+=calc(x);
        }
    }
    return ret;
}

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4696 KB	Output is correct
2	Correct	1 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	4444 KB	Output is correct
6	Correct	2 ms	4700 KB	Output is correct

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	10448 KB	Output is correct
2	Correct	45 ms	11724 KB	Output is correct
3	Correct	61 ms	10448 KB	Output is correct
4	Correct	47 ms	11408 KB	Output is correct
5	Correct	45 ms	10440 KB	Output is correct
6	Correct	46 ms	11904 KB	Output is correct

Subtask #3
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	11280 KB	Output is correct
2	Correct	46 ms	10708 KB	Output is correct
3	Correct	53 ms	11204 KB	Output is correct
4	Correct	53 ms	10708 KB	Output is correct
5	Correct	54 ms	11208 KB	Output is correct
6	Correct	55 ms	11464 KB	Output is correct

Subtask #4
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4696 KB	Output is correct
2	Correct	1 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	4444 KB	Output is correct
6	Correct	2 ms	4700 KB	Output is correct
7	Correct	2 ms	4444 KB	Output is correct
8	Correct	2 ms	4700 KB	Output is correct
9	Correct	2 ms	4584 KB	Output is correct
10	Correct	2 ms	4700 KB	Output is correct
11	Correct	2 ms	4700 KB	Output is correct
12	Correct	2 ms	4444 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4696 KB	Output is correct
2	Correct	1 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	4444 KB	Output is correct
6	Correct	2 ms	4700 KB	Output is correct
7	Correct	44 ms	10448 KB	Output is correct
8	Correct	45 ms	11724 KB	Output is correct
9	Correct	61 ms	10448 KB	Output is correct
10	Correct	47 ms	11408 KB	Output is correct
11	Correct	45 ms	10440 KB	Output is correct
12	Correct	46 ms	11904 KB	Output is correct
13	Correct	46 ms	11280 KB	Output is correct
14	Correct	46 ms	10708 KB	Output is correct
15	Correct	53 ms	11204 KB	Output is correct
16	Correct	53 ms	10708 KB	Output is correct
17	Correct	54 ms	11208 KB	Output is correct
18	Correct	55 ms	11464 KB	Output is correct
19	Correct	2 ms	4444 KB	Output is correct
20	Correct	2 ms	4700 KB	Output is correct
21	Correct	2 ms	4584 KB	Output is correct
22	Correct	2 ms	4700 KB	Output is correct
23	Correct	2 ms	4700 KB	Output is correct
24	Correct	2 ms	4444 KB	Output is correct
25	Correct	51 ms	10444 KB	Output is correct
26	Correct	51 ms	10448 KB	Output is correct
27	Correct	60 ms	11468 KB	Output is correct
28	Correct	61 ms	11720 KB	Output is correct
29	Correct	64 ms	10440 KB	Output is correct
30	Correct	61 ms	10444 KB	Output is correct

Subtask #6
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	11280 KB	Output is correct
2	Correct	46 ms	10708 KB	Output is correct
3	Correct	53 ms	11204 KB	Output is correct
4	Correct	53 ms	10708 KB	Output is correct
5	Correct	54 ms	11208 KB	Output is correct
6	Correct	55 ms	11464 KB	Output is correct
7	Correct	73 ms	15188 KB	Output is correct
8	Correct	76 ms	14532 KB	Output is correct
9	Correct	83 ms	14532 KB	Output is correct
10	Correct	80 ms	14536 KB	Output is correct
11	Correct	77 ms	15816 KB	Output is correct
12	Correct	79 ms	14792 KB	Output is correct
13	Correct	83 ms	15084 KB	Output is correct
14	Correct	82 ms	16072 KB	Output is correct
15	Correct	91 ms	15304 KB	Output is correct

Subtask #7
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4696 KB	Output is correct
3	Correct	1 ms	4700 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	2 ms	4700 KB	Output is correct
6	Correct	2 ms	4444 KB	Output is correct
7	Correct	2 ms	4700 KB	Output is correct
8	Correct	44 ms	10448 KB	Output is correct
9	Correct	45 ms	11724 KB	Output is correct
10	Correct	61 ms	10448 KB	Output is correct
11	Correct	47 ms	11408 KB	Output is correct
12	Correct	45 ms	10440 KB	Output is correct
13	Correct	46 ms	11904 KB	Output is correct
14	Correct	46 ms	11280 KB	Output is correct
15	Correct	46 ms	10708 KB	Output is correct
16	Correct	53 ms	11204 KB	Output is correct
17	Correct	53 ms	10708 KB	Output is correct
18	Correct	54 ms	11208 KB	Output is correct
19	Correct	55 ms	11464 KB	Output is correct
20	Correct	2 ms	4444 KB	Output is correct
21	Correct	2 ms	4700 KB	Output is correct
22	Correct	2 ms	4584 KB	Output is correct
23	Correct	2 ms	4700 KB	Output is correct
24	Correct	2 ms	4700 KB	Output is correct
25	Correct	2 ms	4444 KB	Output is correct
26	Correct	51 ms	10444 KB	Output is correct
27	Correct	51 ms	10448 KB	Output is correct
28	Correct	60 ms	11468 KB	Output is correct
29	Correct	61 ms	11720 KB	Output is correct
30	Correct	64 ms	10440 KB	Output is correct
31	Correct	61 ms	10444 KB	Output is correct
32	Correct	73 ms	15188 KB	Output is correct
33	Correct	76 ms	14532 KB	Output is correct
34	Correct	83 ms	14532 KB	Output is correct
35	Correct	80 ms	14536 KB	Output is correct
36	Correct	77 ms	15816 KB	Output is correct
37	Correct	79 ms	14792 KB	Output is correct
38	Correct	83 ms	15084 KB	Output is correct
39	Correct	82 ms	16072 KB	Output is correct
40	Correct	91 ms	15304 KB	Output is correct
41	Correct	80 ms	15048 KB	Output is correct
42	Correct	82 ms	16260 KB	Output is correct
43	Correct	89 ms	15812 KB	Output is correct
44	Correct	81 ms	15816 KB	Output is correct
45	Correct	88 ms	15824 KB	Output is correct
46	Correct	82 ms	15812 KB	Output is correct
47	Correct	81 ms	15560 KB	Output is correct
48	Correct	84 ms	14964 KB	Output is correct
49	Correct	87 ms	15300 KB	Output is correct

Submission #1099751

Compilation message