oj.uz

Submission #1103066

# Submission time Handle Problem Language Result Execution time Memory
1103066 2024-10-19T19:49:31 Z PedroBigMan Nile (IOI24_nile) C++17
100 / 100
 247 ms 58936 KB 
#include "nile.h"
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

class ST
{	
    public:
    ll N;
    
    class SV //seg value
    {
        public:
        ll a; 
        SV() {a=INF;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) {SV ANS(min(a,X.a)); return ANS;}
    };
      
    class LV //lazy value
    {
        public:
        ll a;
        LV() {a=0LL;}
        LV(ll x) {a=x;}
        
        LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
    };
    
    SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
    {
        SV X(p[c].a+lazy[c].a);
        return X;
    }
    
    SV neuts; LV neutl;
    
    vector<SV> p;
    vector<LV> lazy;
    vector<pl> range;
    
    ST() {N=0LL;}
    ST(vector<ll> arr)
    {
        N = (ll) 1<<(ll) ceil(log2(arr.size()));
        REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
        REP(i,0,N) {p.pb(neuts);}
        REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i);}
        REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i);}
        ll cur = N-1;
        while(cur>0)
        {
            p[cur]=p[2*cur]&p[2*cur+1];
            range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
            cur--;
        }
        REP(i,0,2*N) {lazy.pb(neutl);}
    }
    
    void prop(ll c) //how lazy values propagate
    {
        p[c] = upval(c);
        lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
        lazy[c]=neutl;
    }
    
    SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b)
    {
		if(a>b) {return neuts;}
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(c);}
        prop(c);
        SV ans = query(a,b,2*c)&query(a,b,2*c+1);
        return ans;
    }
    
    void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b)
    {
		if(a>b) {return;}
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return ;}
        if(x>=a && y<=b) 
        {
            lazy[c]=s&lazy[c]; 
            return;
        }
		prop(c);
        update(s,a,b,2*c); update(s,a,b,2*c+1);
        p[c]=upval(2*c)&upval(2*c+1);
    }
};

ST S_odd, S_even, S_over_odd, S_over_even;

class DSU //with range compression and union by subtree size
{
    public:
    ll N;
    vector<ll> p,siz; vector<pl> range;
    vector<ll> cost;
    
    DSU(ll n)
    {
        N=n; REP(i,0,N) {p.pb(i); siz.pb(1); range.pb({i,i});}
    }
    
    ll find(ll x)
    {
        if(p[x]==x) {return x;}
        ll ans=find(p[x]);
        p[x]=ans; 
        return ans;
    }

    void update_cost(ll x)
    {
        if(siz[x]%2==0) {cost[x]=0;}
        else
        {
            if(range[x].ff%2==0) {cost[x]=min(S_even.query(range[x].ff,range[x].ss).a,S_over_odd.query(range[x].ff,range[x].ss).a);}
            else {cost[x]=min(S_odd.query(range[x].ff,range[x].ss).a,S_over_even.query(range[x].ff,range[x].ss).a);}
        }
    }
    
    void unionn(ll a, ll b)
    {
        a=find(a); b=find(b);
		if(a==b) {return;}
        if(siz[a]>siz[b]) {swap(a,b);}
        p[a]=b; siz[b]+=siz[a];
        range[b] = {min(range[a].ff,range[b].ff),max(range[a].ss,range[b].ss)};
        update_cost(b);
    }
	
	vector<vector<ll> > EquivalenceClasses() //O(N)
	{
		vector<vector<ll> > rep; REP(i,0,N) {rep.pb({});}
		REP(i,0,N) {rep[find(i)].pb(i);}
		vector<vector<ll> > CC; 
		REP(i,0,N) {if(rep[i].size()>0) {CC.pb(rep[i]);}}
		return CC;
	}
};

vector<ll> calculate_costs(vector<int> weights, vector<int> AA, vector<int> BB, vector<int> E) 
{
    ll N = weights.size(); ll Q = E.size();
    vector<pl> weights_order; REP(i,0,N) {weights_order.pb({weights[i],i});}
    sort(whole(weights_order));
    vector<ll> w(N,0);
    vector<ll> cost(N,0); ll ind;
    ll basis_cost = 0; REP(i,0,N) {ind = weights_order[i].ss; w[i]=weights[ind]; basis_cost+=BB[ind]; cost[i]=AA[ind]-BB[ind];}
    vector<pl> queries; REP(q,0,Q) {queries.pb({E[q],q});}
    sort(whole(queries)); 
    DSU X(N); X.cost = cost;
    vector<pl> dist,dist_double;
    REP(i,0,N-1) {dist.pb({w[i+1]-w[i],i});}
    REP(i,1,N-1) {dist_double.pb({w[i+1]-w[i-1],i});}
    sort(whole(dist)); sort(whole(dist_double));
    vector<ll> ans(Q,0); ll query_ind; ll D;
    ll dist_ind=0; ll dist_double_ind=0;
    ll curans=0; REP(i,0,N) {curans+=cost[i];}
    ll A,B;
    vector<ll> xx(N,INF); S_even = ST(xx); S_odd = ST(xx); S_over_even = ST(xx); S_over_odd = ST(xx);
    REP(i,0,N)
    {
        if(i%2==0) {S_even.update(cost[i]-INF,i,i);}
        else {S_odd.update(cost[i]-INF,i,i);}
    }
    REP(q,0,Q)
    {
        query_ind = queries[q].ss; D = queries[q].ff; 
        while(dist_ind < dist.size() && dist[dist_ind].ff<=D)
        {
            ind = dist[dist_ind].ss;
            A = X.find(ind); B = X.find(ind+1);
            curans-=X.cost[A]; curans-=X.cost[B];
            X.unionn(A,B); A = X.find(A); curans+=X.cost[A];
            dist_ind++;
        }
        while(dist_double_ind < dist_double.size() && dist_double[dist_double_ind].ff<=D)
        {
            ind = dist_double[dist_double_ind].ss;
            if(ind%2==0) {S_over_even.update(cost[ind]-INF,ind,ind);}
            else {S_over_odd.update(cost[ind]-INF,ind,ind);}
            A = X.find(ind); curans-=X.cost[A];
            X.update_cost(A); curans+=X.cost[A];
            dist_double_ind++;
        }
        ans[query_ind]=curans+basis_cost;
    }
    return ans;
}

Compilation message

nile.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
nile.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:214:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |         while(dist_ind < dist.size() && dist[dist_ind].ff<=D)
      |               ~~~~~~~~~^~~~~~~~~~~~~
nile.cpp:222:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |         while(dist_double_ind < dist_double.size() && dist_double[dist_double_ind].ff<=D)
      |               ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1104 KB Output is correct
2 Correct 3 ms 1276 KB Output is correct
3 Correct 4 ms 1116 KB Output is correct
4 Correct 3 ms 1284 KB Output is correct
5 Correct 3 ms 1104 KB Output is correct
6 Correct 3 ms 1104 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 51636 KB Output is correct
2 Correct 161 ms 54264 KB Output is correct
3 Correct 146 ms 54224 KB Output is correct
4 Correct 121 ms 53920 KB Output is correct
5 Correct 123 ms 53428 KB Output is correct
6 Correct 122 ms 51648 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 52848 KB Output is correct
2 Correct 164 ms 51636 KB Output is correct
3 Correct 188 ms 52660 KB Output is correct
4 Correct 190 ms 52664 KB Output is correct
5 Correct 158 ms 51636 KB Output is correct
6 Correct 170 ms 52928 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1104 KB Output is correct
2 Correct 3 ms 1276 KB Output is correct
3 Correct 4 ms 1116 KB Output is correct
4 Correct 3 ms 1284 KB Output is correct
5 Correct 3 ms 1104 KB Output is correct
6 Correct 3 ms 1104 KB Output is correct
7 Correct 3 ms 1104 KB Output is correct
8 Correct 3 ms 1104 KB Output is correct
9 Correct 4 ms 1104 KB Output is correct
10 Correct 4 ms 1104 KB Output is correct
11 Correct 3 ms 1244 KB Output is correct
12 Correct 4 ms 1104 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1104 KB Output is correct
2 Correct 3 ms 1276 KB Output is correct
3 Correct 4 ms 1116 KB Output is correct
4 Correct 3 ms 1284 KB Output is correct
5 Correct 3 ms 1104 KB Output is correct
6 Correct 3 ms 1104 KB Output is correct
7 Correct 143 ms 51636 KB Output is correct
8 Correct 161 ms 54264 KB Output is correct
9 Correct 146 ms 54224 KB Output is correct
10 Correct 121 ms 53920 KB Output is correct
11 Correct 123 ms 53428 KB Output is correct
12 Correct 122 ms 51648 KB Output is correct
13 Correct 149 ms 52848 KB Output is correct
14 Correct 164 ms 51636 KB Output is correct
15 Correct 188 ms 52660 KB Output is correct
16 Correct 190 ms 52664 KB Output is correct
17 Correct 158 ms 51636 KB Output is correct
18 Correct 170 ms 52928 KB Output is correct
19 Correct 3 ms 1104 KB Output is correct
20 Correct 3 ms 1104 KB Output is correct
21 Correct 4 ms 1104 KB Output is correct
22 Correct 4 ms 1104 KB Output is correct
23 Correct 3 ms 1244 KB Output is correct
24 Correct 4 ms 1104 KB Output is correct
25 Correct 152 ms 54560 KB Output is correct
26 Correct 171 ms 51816 KB Output is correct
27 Correct 198 ms 54200 KB Output is correct
28 Correct 217 ms 51892 KB Output is correct
29 Correct 177 ms 54292 KB Output is correct
30 Correct 186 ms 54196 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 52848 KB Output is correct
2 Correct 164 ms 51636 KB Output is correct
3 Correct 188 ms 52660 KB Output is correct
4 Correct 190 ms 52664 KB Output is correct
5 Correct 158 ms 51636 KB Output is correct
6 Correct 170 ms 52928 KB Output is correct
7 Correct 157 ms 55348 KB Output is correct
8 Correct 215 ms 57396 KB Output is correct
9 Correct 237 ms 55232 KB Output is correct
10 Correct 213 ms 57216 KB Output is correct
11 Correct 247 ms 55548 KB Output is correct
12 Correct 234 ms 55608 KB Output is correct
13 Correct 224 ms 55356 KB Output is correct
14 Correct 177 ms 57140 KB Output is correct
15 Correct 206 ms 55352 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 1104 KB Output is correct
3 Correct 3 ms 1276 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 3 ms 1284 KB Output is correct
6 Correct 3 ms 1104 KB Output is correct
7 Correct 3 ms 1104 KB Output is correct
8 Correct 143 ms 51636 KB Output is correct
9 Correct 161 ms 54264 KB Output is correct
10 Correct 146 ms 54224 KB Output is correct
11 Correct 121 ms 53920 KB Output is correct
12 Correct 123 ms 53428 KB Output is correct
13 Correct 122 ms 51648 KB Output is correct
14 Correct 149 ms 52848 KB Output is correct
15 Correct 164 ms 51636 KB Output is correct
16 Correct 188 ms 52660 KB Output is correct
17 Correct 190 ms 52664 KB Output is correct
18 Correct 158 ms 51636 KB Output is correct
19 Correct 170 ms 52928 KB Output is correct
20 Correct 3 ms 1104 KB Output is correct
21 Correct 3 ms 1104 KB Output is correct
22 Correct 4 ms 1104 KB Output is correct
23 Correct 4 ms 1104 KB Output is correct
24 Correct 3 ms 1244 KB Output is correct
25 Correct 4 ms 1104 KB Output is correct
26 Correct 152 ms 54560 KB Output is correct
27 Correct 171 ms 51816 KB Output is correct
28 Correct 198 ms 54200 KB Output is correct
29 Correct 217 ms 51892 KB Output is correct
30 Correct 177 ms 54292 KB Output is correct
31 Correct 186 ms 54196 KB Output is correct
32 Correct 157 ms 55348 KB Output is correct
33 Correct 215 ms 57396 KB Output is correct
34 Correct 237 ms 55232 KB Output is correct
35 Correct 213 ms 57216 KB Output is correct
36 Correct 247 ms 55548 KB Output is correct
37 Correct 234 ms 55608 KB Output is correct
38 Correct 224 ms 55356 KB Output is correct
39 Correct 177 ms 57140 KB Output is correct
40 Correct 206 ms 55352 KB Output is correct
41 Correct 168 ms 55348 KB Output is correct
42 Correct 204 ms 55860 KB Output is correct
43 Correct 222 ms 55292 KB Output is correct
44 Correct 218 ms 58932 KB Output is correct
45 Correct 212 ms 58920 KB Output is correct
46 Correct 212 ms 58936 KB Output is correct
47 Correct 208 ms 55352 KB Output is correct
48 Correct 176 ms 58548 KB Output is correct
49 Correct 204 ms 58684 KB Output is correct