Submission #1287329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287329		liangjeremy	Nile (IOI24_nile)	C++20	100 / 100	438 ms	67764 KiB

nile

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#include "nile.h"
#define fi first
#define se second
#define int long long
using namespace std;
//using namespace __gnu_pbds;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
	int a; int b; int w; 
};
bool cmp(node q, node z){
	return q.w<z.w; 
}
struct querys{
	int d; int idx; 
};
bool cmpq(querys a, querys b){
	return a.d<b.d; 
}

const int MAXN=3; 
struct Matrix{
    int mat[3+1][3+1]; int h=3; int w=3; //int h,w;
    Matrix(){ 
    	memset(mat,0,sizeof(mat)); 
    }
    void build(){
    	for(int i=1; i<=3; i++){
    		for(int j=1; j<=3; j++){
    			mat[i][j]=1e18; 
    		}
    	}
    }
};
Matrix operator*(const Matrix &a, const Matrix &b){
    Matrix c; c.build(); //c.h=a.w; c.w=b.w;
    for(int i=1; i<=a.h; i++){
        for(int j=1; j<=b.w; j++){
            for(int k=1; k<=a.w; k++){
                c.mat[i][j]=min(c.mat[i][j],a.mat[i][k]+b.mat[k][j]);
            }
        }
    }
    return c;
};

const int maxn=1e5+10; Matrix sum[maxn<<2]; Matrix d; int f1; int f2; 
void build(int l, int r, int rt, const vector<node>&v){
	if(l==r){
		sum[rt].build(); sum[rt].mat[1][1]=v[l].a; sum[rt].mat[2][1]=0; sum[rt].mat[3][2]=0; return;
	}
	int mid=(l+r)>>1; build(l,mid,rt<<1,v); build(mid+1,r,rt<<1|1,v); 
	sum[rt]=sum[rt<<1|1]*sum[rt<<1]; 
}
void update(int l, int r, int rt, int idx){
	if(l==r){
		if(l==2){
			sum[rt].mat[1][1]=f2; sum[rt].mat[2][1]=f1; sum[rt].mat[3][1]=0; return; 
		}
		sum[rt]=d; return; 
	}
	int mid=(l+r)>>1; 
	if(idx<=mid)update(l,mid,rt<<1,idx); else update(mid+1,r,rt<<1|1,idx); 
	if(l==1 && r==2)sum[rt]=sum[rt<<1|1]; else sum[rt]=sum[rt<<1|1]*sum[rt<<1]; 
}

vector<int>calculate_costs(vector<int32_t>W, vector<int32_t>A, vector<int32_t>B, vector<int32_t>E){
	int n=W.size(); int q=E.size(); vector<node>v(n+1); vector<querys>qry(q); 
	for(int i=1; i<=n; i++){
		v[i].a=A[i-1]; v[i].b=B[i-1]; v[i].w=W[i-1]; 
	}
	sort(v.begin()+1,v.end(),cmp); vector<pair<int,int>>v1; vector<pair<int,int>>v2; 
	for(int i=2; i<=n; i++){
		v1.push_back({v[i].w-v[i-1].w,i}); 
		if(i>=3)v2.push_back({v[i].w-v[i-2].w,i}); 
	}
	for(int i=0; i<q; i++){
		qry[i].d=E[i]; qry[i].idx=i; 
	}
	sort(qry.begin(),qry.end(),cmpq); vector<int>ans(q); build(1,n,1,v); 
	sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end()); int x=0; int y=0; 
	for(int i=0; i<q; i++){
		f1=v[1].a; if(v[2].w-v[1].w<=qry[i].d)f2=v[1].b+v[2].b; else f2=v[2].a+v[1].a; 
		update(1,n,1,2); d.build(); d.mat[2][1]=0; d.mat[3][2]=0; 
		while(x<v1.size() && v1[x].fi<=qry[i].d){
			int idx=v1[x].se; d.mat[1][1]=v[idx].a; d.mat[1][2]=v[idx].b+v[idx-1].b; x++; update(1,n,1,idx); 
		}
		while(y<v2.size() && v2[y].fi<=qry[i].d){
			int idx=v2[y].se; d.mat[1][1]=v[idx].a; d.mat[1][2]=v[idx].b+v[idx-1].b; 
			d.mat[1][3]=v[idx].b+v[idx-1].a+v[idx-2].b; y++; update(1,n,1,idx); 
		}
		ans[qry[i].idx]=sum[1].mat[1][1]; 
	}
	return ans; 
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18