oj.uz

Submission #377222

# Submission time Handle Problem Language Result Execution time Memory
377222 2021-03-13T13:00:02 Z Jasiekstrz Aliens (IOI16_aliens) C++17
16 / 100
 3 ms 2156 KB 
#include<bits/stdc++.h>
#include "aliens.h"
#define fi first
#define se second
using namespace std;

const long long INF=(long long)1e18+7;
const int N=1e5;

struct Interval
{
	long long l,r;

	Interval(int row=-1,int col=-1)
	{
		l=row;
		r=col;
		if(l>r)
			swap(l,r);
		return;
	}
	inline bool operator<(const Interval &oth) const
	{
		if(l==oth.l)
			return r>oth.r;
		return l<oth.l;
	}
	inline long long common(Interval oth)
	{
		if(oth.r<l || r<oth.l)
			return 0;
		if(oth.r>r)
			return r-oth.l+1;
		return oth.r-l+1;
	}
	inline long long size()
	{
		return r-l+1;
	}
};

struct Ans
{
	long long w,k;

	Ans(long long _w=0,long long _k=0) : w(_w),k(_k) {}
};

struct Function
{
	long long a,b;
	int id;

	Function(long long _a,long long _b,int _id) : a(_a),b(_b),id(_id) {}
	inline long long f(long long x)
	{
		return x*x+a*x+b;
	}
	inline long long better(Function &oth)
	{
		if(oth.a==a)
			return INF;
		return (oth.b-b+a-oth.a)/(a-oth.a);
	}
};

Interval tab[N+10];
long long dp[N+10];
int kk[N+10];
long long cross[N+10];
deque<Function> dq;

inline bool try_pop(int i)
{
	if(dq.size()<2)
		return false;
	Function t=dq.front();
	dq.pop_front();
	if(dq.front().f(tab[i].r)<t.f(tab[i].r))
		return true;
	dq.push_front(t);
	return false;
}

inline bool try_pop_back(Function &x)
{
	if(dq.size()<2)
		return false;
	if(x.f(cross[dq.back().id])<dq.back().f(cross[dq.back().id]))
	{
		dq.pop_back();
		return true;
	}
	return false;
}

inline void try_push(int i,long long c)
{
	Function t(-2*(tab[i+1].l-1),dp[i]+c+(tab[i+1].l-1)*(tab[i+1].l-1),i);
	while(try_pop_back(t));
	if(!dq.empty())
		cross[i]=t.better(dq.back());
	dq.push_back(t);
	return;
}

inline Ans solve(int n,long long c)
{
	int i;
	dq.clear();
	dp[0]=0;
	kk[0]=0;
	try_push(0,c);
	for(i=1;i<=n;i++)
	{
		while(try_pop(i));
		kk[i]=kk[dq.front().id]+1;
		dp[i]=dq.front().f(tab[i].r);
		try_push(i,c);
	}
	return Ans(dp[n],kk[n]);
}

long long take_photos(int n,int m,int k,vector<int> r,vector<int> c)
{
	int i,j;
	long long ans=0;
	for(i=1;i<=n;i++)
	{
		tab[i]=Interval(r[i-1],c[i-1]);
	}
	sort(tab+1,tab+n+1);
	for(i=1,j=-1;i<=n;i++)
	{
		if(tab[i].r<=j)
			tab[i].l=m+1;
		j=max(j,(int)tab[i].r);
	}
	sort(tab+1,tab+n+1);
	for(i=1;i<=n && tab[i].l<m;i++);
	n=i-1;
	tab[0]=Interval(-1,-1);
	tab[n+1]=Interval(m+1,m+1);
	if(n<=k)
	{
		for(i=1;i<=n;i++)
			ans+=tab[i].size()*tab[i].size()-tab[i].common(tab[i-1])*tab[i].common(tab[i-1]);
		return ans;
	}
	long long bg=0,en=(long long)m*m,mid;
	while(bg<en)
	{
		mid=(bg+en)/2;
		Ans tmp=solve(n,mid);
		if(tmp.k<=k)
			en=mid;
		else
			bg=mid+1;
	}
	Ans tmp=solve(n,bg);
    return tmp.w-bg*k;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Correct answer: answer = 4
2 Correct 2 ms 1900 KB Correct answer: answer = 4
3 Correct 1 ms 1900 KB Correct answer: answer = 4
4 Correct 2 ms 1848 KB Correct answer: answer = 12
5 Correct 1 ms 1900 KB Correct answer: answer = 52
6 Correct 1 ms 1900 KB Correct answer: answer = 210
7 Correct 2 ms 1900 KB Correct answer: answer = 88
8 Correct 2 ms 1900 KB Correct answer: answer = 7696
9 Correct 2 ms 1900 KB Correct answer: answer = 1
10 Correct 1 ms 1900 KB Correct answer: answer = 2374
11 Correct 1 ms 1900 KB Correct answer: answer = 9502
12 Correct 2 ms 1900 KB Correct answer: answer = 49
13 Correct 1 ms 1900 KB Correct answer: answer = 151
14 Correct 2 ms 1900 KB Correct answer: answer = 7550
15 Correct 2 ms 1900 KB Correct answer: answer = 7220
16 Correct 1 ms 1900 KB Correct answer: answer = 7550
17 Correct 1 ms 1900 KB Correct answer: answer = 10000
18 Correct 2 ms 1900 KB Correct answer: answer = 10000
19 Correct 2 ms 1900 KB Correct answer: answer = 624
20 Correct 2 ms 1900 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Correct answer: answer = 1
2 Correct 1 ms 1900 KB Correct answer: answer = 4
3 Correct 2 ms 1900 KB Correct answer: answer = 1
4 Correct 2 ms 1900 KB Correct answer: answer = 5
5 Correct 1 ms 1920 KB Correct answer: answer = 41
6 Correct 2 ms 1900 KB Correct answer: answer = 71923
7 Correct 2 ms 1900 KB Correct answer: answer = 77137
8 Correct 2 ms 1900 KB Correct answer: answer = 764
9 Correct 2 ms 2028 KB Correct answer: answer = 250000
10 Correct 2 ms 2048 KB Correct answer: answer = 500
11 Correct 1 ms 1900 KB Correct answer: answer = 32
12 Correct 2 ms 2028 KB Correct answer: answer = 130050
13 Correct 2 ms 1900 KB Correct answer: answer = 5110
14 Correct 2 ms 1900 KB Correct answer: answer = 2626
15 Correct 2 ms 1920 KB Correct answer: answer = 796
16 Correct 2 ms 1900 KB Correct answer: answer = 7580
17 Correct 2 ms 1900 KB Correct answer: answer = 1904
18 Correct 2 ms 1900 KB Correct answer: answer = 996004
19 Correct 2 ms 1900 KB Correct answer: answer = 38817
20 Correct 3 ms 1900 KB Correct answer: answer = 4096
21 Correct 2 ms 1900 KB Correct answer: answer = 1
22 Correct 2 ms 1900 KB Correct answer: answer = 1
23 Correct 2 ms 1900 KB Correct answer: answer = 2040
24 Correct 2 ms 1900 KB Correct answer: answer = 2

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Correct answer: answer = 4
2 Correct 2 ms 1900 KB Correct answer: answer = 4
3 Correct 1 ms 1900 KB Correct answer: answer = 4
4 Correct 2 ms 1848 KB Correct answer: answer = 12
5 Correct 1 ms 1900 KB Correct answer: answer = 52
6 Correct 1 ms 1900 KB Correct answer: answer = 210
7 Correct 2 ms 1900 KB Correct answer: answer = 88
8 Correct 2 ms 1900 KB Correct answer: answer = 7696
9 Correct 2 ms 1900 KB Correct answer: answer = 1
10 Correct 1 ms 1900 KB Correct answer: answer = 2374
11 Correct 1 ms 1900 KB Correct answer: answer = 9502
12 Correct 2 ms 1900 KB Correct answer: answer = 49
13 Correct 1 ms 1900 KB Correct answer: answer = 151
14 Correct 2 ms 1900 KB Correct answer: answer = 7550
15 Correct 2 ms 1900 KB Correct answer: answer = 7220
16 Correct 1 ms 1900 KB Correct answer: answer = 7550
17 Correct 1 ms 1900 KB Correct answer: answer = 10000
18 Correct 2 ms 1900 KB Correct answer: answer = 10000
19 Correct 2 ms 1900 KB Correct answer: answer = 624
20 Correct 2 ms 1900 KB Correct answer: answer = 10000
21 Correct 1 ms 1900 KB Correct answer: answer = 1
22 Correct 1 ms 1900 KB Correct answer: answer = 4
23 Correct 2 ms 1900 KB Correct answer: answer = 1
24 Correct 2 ms 1900 KB Correct answer: answer = 5
25 Correct 1 ms 1920 KB Correct answer: answer = 41
26 Correct 2 ms 1900 KB Correct answer: answer = 71923
27 Correct 2 ms 1900 KB Correct answer: answer = 77137
28 Correct 2 ms 1900 KB Correct answer: answer = 764
29 Correct 2 ms 2028 KB Correct answer: answer = 250000
30 Correct 2 ms 2048 KB Correct answer: answer = 500
31 Correct 1 ms 1900 KB Correct answer: answer = 32
32 Correct 2 ms 2028 KB Correct answer: answer = 130050
33 Correct 2 ms 1900 KB Correct answer: answer = 5110
34 Correct 2 ms 1900 KB Correct answer: answer = 2626
35 Correct 2 ms 1920 KB Correct answer: answer = 796
36 Correct 2 ms 1900 KB Correct answer: answer = 7580
37 Correct 2 ms 1900 KB Correct answer: answer = 1904
38 Correct 2 ms 1900 KB Correct answer: answer = 996004
39 Correct 2 ms 1900 KB Correct answer: answer = 38817
40 Correct 3 ms 1900 KB Correct answer: answer = 4096
41 Correct 2 ms 1900 KB Correct answer: answer = 1
42 Correct 2 ms 1900 KB Correct answer: answer = 1
43 Correct 2 ms 1900 KB Correct answer: answer = 2040
44 Correct 2 ms 1900 KB Correct answer: answer = 2
45 Correct 1 ms 1900 KB Correct answer: answer = 4
46 Correct 1 ms 1900 KB Correct answer: answer = 9
47 Correct 2 ms 2156 KB Correct answer: answer = 9
48 Correct 2 ms 1900 KB Correct answer: answer = 21
49 Incorrect 1 ms 1900 KB Wrong answer: output = 80, expected = 71
50 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Correct answer: answer = 4
2 Correct 2 ms 1900 KB Correct answer: answer = 4
3 Correct 1 ms 1900 KB Correct answer: answer = 4
4 Correct 2 ms 1848 KB Correct answer: answer = 12
5 Correct 1 ms 1900 KB Correct answer: answer = 52
6 Correct 1 ms 1900 KB Correct answer: answer = 210
7 Correct 2 ms 1900 KB Correct answer: answer = 88
8 Correct 2 ms 1900 KB Correct answer: answer = 7696
9 Correct 2 ms 1900 KB Correct answer: answer = 1
10 Correct 1 ms 1900 KB Correct answer: answer = 2374
11 Correct 1 ms 1900 KB Correct answer: answer = 9502
12 Correct 2 ms 1900 KB Correct answer: answer = 49
13 Correct 1 ms 1900 KB Correct answer: answer = 151
14 Correct 2 ms 1900 KB Correct answer: answer = 7550
15 Correct 2 ms 1900 KB Correct answer: answer = 7220
16 Correct 1 ms 1900 KB Correct answer: answer = 7550
17 Correct 1 ms 1900 KB Correct answer: answer = 10000
18 Correct 2 ms 1900 KB Correct answer: answer = 10000
19 Correct 2 ms 1900 KB Correct answer: answer = 624
20 Correct 2 ms 1900 KB Correct answer: answer = 10000
21 Correct 1 ms 1900 KB Correct answer: answer = 1
22 Correct 1 ms 1900 KB Correct answer: answer = 4
23 Correct 2 ms 1900 KB Correct answer: answer = 1
24 Correct 2 ms 1900 KB Correct answer: answer = 5
25 Correct 1 ms 1920 KB Correct answer: answer = 41
26 Correct 2 ms 1900 KB Correct answer: answer = 71923
27 Correct 2 ms 1900 KB Correct answer: answer = 77137
28 Correct 2 ms 1900 KB Correct answer: answer = 764
29 Correct 2 ms 2028 KB Correct answer: answer = 250000
30 Correct 2 ms 2048 KB Correct answer: answer = 500
31 Correct 1 ms 1900 KB Correct answer: answer = 32
32 Correct 2 ms 2028 KB Correct answer: answer = 130050
33 Correct 2 ms 1900 KB Correct answer: answer = 5110
34 Correct 2 ms 1900 KB Correct answer: answer = 2626
35 Correct 2 ms 1920 KB Correct answer: answer = 796
36 Correct 2 ms 1900 KB Correct answer: answer = 7580
37 Correct 2 ms 1900 KB Correct answer: answer = 1904
38 Correct 2 ms 1900 KB Correct answer: answer = 996004
39 Correct 2 ms 1900 KB Correct answer: answer = 38817
40 Correct 3 ms 1900 KB Correct answer: answer = 4096
41 Correct 2 ms 1900 KB Correct answer: answer = 1
42 Correct 2 ms 1900 KB Correct answer: answer = 1
43 Correct 2 ms 1900 KB Correct answer: answer = 2040
44 Correct 2 ms 1900 KB Correct answer: answer = 2
45 Correct 1 ms 1900 KB Correct answer: answer = 4
46 Correct 1 ms 1900 KB Correct answer: answer = 9
47 Correct 2 ms 2156 KB Correct answer: answer = 9
48 Correct 2 ms 1900 KB Correct answer: answer = 21
49 Incorrect 1 ms 1900 KB Wrong answer: output = 80, expected = 71
50 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Correct answer: answer = 4
2 Correct 2 ms 1900 KB Correct answer: answer = 4
3 Correct 1 ms 1900 KB Correct answer: answer = 4
4 Correct 2 ms 1848 KB Correct answer: answer = 12
5 Correct 1 ms 1900 KB Correct answer: answer = 52
6 Correct 1 ms 1900 KB Correct answer: answer = 210
7 Correct 2 ms 1900 KB Correct answer: answer = 88
8 Correct 2 ms 1900 KB Correct answer: answer = 7696
9 Correct 2 ms 1900 KB Correct answer: answer = 1
10 Correct 1 ms 1900 KB Correct answer: answer = 2374
11 Correct 1 ms 1900 KB Correct answer: answer = 9502
12 Correct 2 ms 1900 KB Correct answer: answer = 49
13 Correct 1 ms 1900 KB Correct answer: answer = 151
14 Correct 2 ms 1900 KB Correct answer: answer = 7550
15 Correct 2 ms 1900 KB Correct answer: answer = 7220
16 Correct 1 ms 1900 KB Correct answer: answer = 7550
17 Correct 1 ms 1900 KB Correct answer: answer = 10000
18 Correct 2 ms 1900 KB Correct answer: answer = 10000
19 Correct 2 ms 1900 KB Correct answer: answer = 624
20 Correct 2 ms 1900 KB Correct answer: answer = 10000
21 Correct 1 ms 1900 KB Correct answer: answer = 1
22 Correct 1 ms 1900 KB Correct answer: answer = 4
23 Correct 2 ms 1900 KB Correct answer: answer = 1
24 Correct 2 ms 1900 KB Correct answer: answer = 5
25 Correct 1 ms 1920 KB Correct answer: answer = 41
26 Correct 2 ms 1900 KB Correct answer: answer = 71923
27 Correct 2 ms 1900 KB Correct answer: answer = 77137
28 Correct 2 ms 1900 KB Correct answer: answer = 764
29 Correct 2 ms 2028 KB Correct answer: answer = 250000
30 Correct 2 ms 2048 KB Correct answer: answer = 500
31 Correct 1 ms 1900 KB Correct answer: answer = 32
32 Correct 2 ms 2028 KB Correct answer: answer = 130050
33 Correct 2 ms 1900 KB Correct answer: answer = 5110
34 Correct 2 ms 1900 KB Correct answer: answer = 2626
35 Correct 2 ms 1920 KB Correct answer: answer = 796
36 Correct 2 ms 1900 KB Correct answer: answer = 7580
37 Correct 2 ms 1900 KB Correct answer: answer = 1904
38 Correct 2 ms 1900 KB Correct answer: answer = 996004
39 Correct 2 ms 1900 KB Correct answer: answer = 38817
40 Correct 3 ms 1900 KB Correct answer: answer = 4096
41 Correct 2 ms 1900 KB Correct answer: answer = 1
42 Correct 2 ms 1900 KB Correct answer: answer = 1
43 Correct 2 ms 1900 KB Correct answer: answer = 2040
44 Correct 2 ms 1900 KB Correct answer: answer = 2
45 Correct 1 ms 1900 KB Correct answer: answer = 4
46 Correct 1 ms 1900 KB Correct answer: answer = 9
47 Correct 2 ms 2156 KB Correct answer: answer = 9
48 Correct 2 ms 1900 KB Correct answer: answer = 21
49 Incorrect 1 ms 1900 KB Wrong answer: output = 80, expected = 71
50 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Correct answer: answer = 4
2 Correct 2 ms 1900 KB Correct answer: answer = 4
3 Correct 1 ms 1900 KB Correct answer: answer = 4
4 Correct 2 ms 1848 KB Correct answer: answer = 12
5 Correct 1 ms 1900 KB Correct answer: answer = 52
6 Correct 1 ms 1900 KB Correct answer: answer = 210
7 Correct 2 ms 1900 KB Correct answer: answer = 88
8 Correct 2 ms 1900 KB Correct answer: answer = 7696
9 Correct 2 ms 1900 KB Correct answer: answer = 1
10 Correct 1 ms 1900 KB Correct answer: answer = 2374
11 Correct 1 ms 1900 KB Correct answer: answer = 9502
12 Correct 2 ms 1900 KB Correct answer: answer = 49
13 Correct 1 ms 1900 KB Correct answer: answer = 151
14 Correct 2 ms 1900 KB Correct answer: answer = 7550
15 Correct 2 ms 1900 KB Correct answer: answer = 7220
16 Correct 1 ms 1900 KB Correct answer: answer = 7550
17 Correct 1 ms 1900 KB Correct answer: answer = 10000
18 Correct 2 ms 1900 KB Correct answer: answer = 10000
19 Correct 2 ms 1900 KB Correct answer: answer = 624
20 Correct 2 ms 1900 KB Correct answer: answer = 10000
21 Correct 1 ms 1900 KB Correct answer: answer = 1
22 Correct 1 ms 1900 KB Correct answer: answer = 4
23 Correct 2 ms 1900 KB Correct answer: answer = 1
24 Correct 2 ms 1900 KB Correct answer: answer = 5
25 Correct 1 ms 1920 KB Correct answer: answer = 41
26 Correct 2 ms 1900 KB Correct answer: answer = 71923
27 Correct 2 ms 1900 KB Correct answer: answer = 77137
28 Correct 2 ms 1900 KB Correct answer: answer = 764
29 Correct 2 ms 2028 KB Correct answer: answer = 250000
30 Correct 2 ms 2048 KB Correct answer: answer = 500
31 Correct 1 ms 1900 KB Correct answer: answer = 32
32 Correct 2 ms 2028 KB Correct answer: answer = 130050
33 Correct 2 ms 1900 KB Correct answer: answer = 5110
34 Correct 2 ms 1900 KB Correct answer: answer = 2626
35 Correct 2 ms 1920 KB Correct answer: answer = 796
36 Correct 2 ms 1900 KB Correct answer: answer = 7580
37 Correct 2 ms 1900 KB Correct answer: answer = 1904
38 Correct 2 ms 1900 KB Correct answer: answer = 996004
39 Correct 2 ms 1900 KB Correct answer: answer = 38817
40 Correct 3 ms 1900 KB Correct answer: answer = 4096
41 Correct 2 ms 1900 KB Correct answer: answer = 1
42 Correct 2 ms 1900 KB Correct answer: answer = 1
43 Correct 2 ms 1900 KB Correct answer: answer = 2040
44 Correct 2 ms 1900 KB Correct answer: answer = 2
45 Correct 1 ms 1900 KB Correct answer: answer = 4
46 Correct 1 ms 1900 KB Correct answer: answer = 9
47 Correct 2 ms 2156 KB Correct answer: answer = 9
48 Correct 2 ms 1900 KB Correct answer: answer = 21
49 Incorrect 1 ms 1900 KB Wrong answer: output = 80, expected = 71
50 Halted 0 ms 0 KB -