oj.uz

Submission #850225

# Submission time Handle Problem Language Result Execution time Memory
850225 2023-09-16T07:22:55 Z Tai_xiu Building Bridges (CEOI17_building) C++14
100 / 100
 57 ms 69528 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100005;
const int len=1000016;
const int oo=1e18;
struct line
{
    long long a,b;
    int operator() (const int x) const {
        return a*x+b;
    }
}t[8*len];
int s[maxn],a[maxn],n;
void build (int v,int tl,int tr)
{
    t[v]={0,oo};
    if (tl==tr){
        return;
    }
    int tm=(tl+tr)>>1;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
}
void update(int v, int tl,int tr,line l)
{
   if (tl==tr){
        if (t[v](tl)>l(tl))
            t[v]=l;
        return;
   }
   int tm=tl+tr>>1;
   if (l.a>t[v].a) swap(t[v],l);
   if (t[v](tm)>l(tm))
        {
            swap(t[v],l);
            update(v*2,tl,tm,l);
        }
    else update(v*2+1,tm+1,tr,l);
}
int query(int v,int tl,int tr,int val)
{
   if (tl==tr)
     return t[v](val);
    int tm=(tl+tr)>>1;
    if (val<tm)
        return min(t[v](val),query(v*2,tl,tm,val));
    return min(t[v](val),query(v*2+1,tm+1,tr,val));
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
   cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	for (int i=1;i<=n;i++){
		cin>>s[i];
		s[i]+=s[i-1];
		//cout<<s[i]<<" ";
	}
	/*
	for (int i=1;i<=n;i++)
		cout<<s[i]<<" ";
	cout<<endl;*/

	build(1,-len,len);
	update(1,-len,len,{a[1],a[1]*a[1]-s[1]});
	for (int i=2;i<n;i++){
		int x=query(1,-len,len,-2*a[i]);
		update(1,-len,len,{a[i],a[i]*a[i]-s[i]+s[i-1]+x+a[i]*a[i]});
		//cout<<(a[i]*a[i])+s[i-1]-s[i]<<'\n';
		//cout<<x<<endl;
		//cout<<x+s[i-1]+a[i]*a[i]<<" ";
	}
	cout<<query(1,-len,len,-2*a[n])+s[n-1]+a[n]*a[n];
}

Compilation message

building.cpp: In function 'void update(long long int, long long int, long long int, line)':
building.cpp:32:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |    int tm=tl+tr>>1;
      |           ~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 67928 KB Output is correct
2 Correct 11 ms 67932 KB Output is correct
3 Correct 12 ms 68304 KB Output is correct
4 Correct 11 ms 68188 KB Output is correct
5 Correct 12 ms 68060 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 69200 KB Output is correct
2 Correct 45 ms 69316 KB Output is correct
3 Correct 45 ms 69212 KB Output is correct
4 Correct 41 ms 69212 KB Output is correct
5 Correct 39 ms 69172 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 67928 KB Output is correct
2 Correct 11 ms 67932 KB Output is correct
3 Correct 12 ms 68304 KB Output is correct
4 Correct 11 ms 68188 KB Output is correct
5 Correct 12 ms 68060 KB Output is correct
6 Correct 45 ms 69200 KB Output is correct
7 Correct 45 ms 69316 KB Output is correct
8 Correct 45 ms 69212 KB Output is correct
9 Correct 41 ms 69212 KB Output is correct
10 Correct 39 ms 69172 KB Output is correct
11 Correct 57 ms 69528 KB Output is correct
12 Correct 52 ms 69200 KB Output is correct
13 Correct 43 ms 69456 KB Output is correct
14 Correct 51 ms 69468 KB Output is correct
15 Correct 38 ms 69204 KB Output is correct
16 Correct 39 ms 69200 KB Output is correct
17 Correct 48 ms 69204 KB Output is correct
18 Correct 45 ms 69360 KB Output is correct