oj.uz

Submission #377053

# Submission time Handle Problem Language Result Execution time Memory
377053 2021-03-12T21:27:58 Z Jasiekstrz Aliens (IOI16_aliens) C++17
4 / 100
 2 ms 1920 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;
	}
};

Interval tab[N+10];
bool on[N+10];
pair<int,int> u[N+10];
set<pair<long long,int>> pq;

inline long long merge_cost(long long l1,long long r1,long long l2,long long r2)
{
	long long c=r2-l1+1,a=r1-l1+1,b=r2-l2+1,d=Interval(l1,r1).common(Interval(l2,r2));
	return c*c-a*a-b*b+d*d;
}
inline long long merge_cost(Interval a,Interval b)
{
	return merge_cost(a.l,a.r,b.l,b.r);
}

inline long long cost(int x,int n)
{
	if(!on[x])
		return merge_cost(tab[u[x-1].fi].l,tab[x-1].r,tab[x].l,tab[u[x].se].r);
	if(on[x] && (x-1>1 && !on[x-1]) && (x+1<=n && !on[x+1]))
	{
		return -merge_cost(tab[x-1],tab[x])
			+merge_cost(tab[u[x-2].fi].l,tab[x-2].r,tab[x-1].l,tab[x-1].r)
			+merge_cost(tab[x].l,tab[x].r,tab[x+1].l,tab[u[x+1].se].r);
	}
	return INF;
}

inline void try_insert(int x,int n)
{
	if(x<=1 || n<x)
		return;
	long long c=cost(x,n);
	if(c>=INF)
		return;
	if(pq.find({c,x})!=pq.end())
		pq.erase({c,x});
	else
		pq.insert({c,x});
	return;
}

inline void upd(int x,int n)
{
	if(!on[x])
	{
		on[x]=true;
		u[u[x].se].fi=u[x-1].fi;
		u[u[x-1].fi].se=u[x].se;
		return;
	}
	on[x]=false;
	on[x-1]=on[x+1]=true;

	u[u[x-2].fi].se=x-1;
	u[x-1]=u[u[x-2].fi];

	u[u[x+1].se].fi=x;
	u[x]=u[u[x+1].se];
	return;
}

long long take_photos(int n,int m,int k,vector<int> r,vector<int> c)
{
	int ki,i,j;
	long long ans=0;
	for(i=1;i<=n;i++)
	{
		tab[i]=Interval(r[i-1],c[i-1]);
		on[i]=false;
		u[i]={i,i};
	}
	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);
	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]);
		try_insert(i,n);
	}
	for(ki=n;ki>k;ki--)
	{
		int x=(pq.begin()->se);
		pq.erase(pq.begin());
		ans+=cost(x,n);
		try_insert(x-1,n);
		try_insert(x+1,n);
		upd(x,n);
		for(int it:{x-1,x,x+1})
			try_insert(it,n);
	}
    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Correct answer: answer = 4
2 Correct 1 ms 1900 KB Correct answer: answer = 4
3 Correct 1 ms 1900 KB Correct answer: answer = 4
4 Correct 1 ms 1900 KB Correct answer: answer = 12
5 Correct 1 ms 1920 KB Correct answer: answer = 52
6 Correct 1 ms 1900 KB Correct answer: answer = 210
7 Correct 1 ms 1900 KB Correct answer: answer = 88
8 Correct 1 ms 1900 KB Correct answer: answer = 7696
9 Correct 1 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 1 ms 1900 KB Correct answer: answer = 49
13 Correct 1 ms 1900 KB Correct answer: answer = 151
14 Correct 1 ms 1900 KB Correct answer: answer = 7550
15 Correct 1 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 1 ms 1900 KB Correct answer: answer = 624
20 Correct 1 ms 1900 KB Correct answer: answer = 10000

Subtask #2
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 1 ms 1900 KB Correct answer: answer = 1
4 Correct 1 ms 1900 KB Correct answer: answer = 5
5 Correct 1 ms 1900 KB Correct answer: answer = 41
6 Incorrect 1 ms 1900 KB Wrong answer: output = 3000000000000020942, expected = 71923
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Correct answer: answer = 4
2 Correct 1 ms 1900 KB Correct answer: answer = 4
3 Correct 1 ms 1900 KB Correct answer: answer = 4
4 Correct 1 ms 1900 KB Correct answer: answer = 12
5 Correct 1 ms 1920 KB Correct answer: answer = 52
6 Correct 1 ms 1900 KB Correct answer: answer = 210
7 Correct 1 ms 1900 KB Correct answer: answer = 88
8 Correct 1 ms 1900 KB Correct answer: answer = 7696
9 Correct 1 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 1 ms 1900 KB Correct answer: answer = 49
13 Correct 1 ms 1900 KB Correct answer: answer = 151
14 Correct 1 ms 1900 KB Correct answer: answer = 7550
15 Correct 1 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 1 ms 1900 KB Correct answer: answer = 624
20 Correct 1 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 1 ms 1900 KB Correct answer: answer = 1
24 Correct 1 ms 1900 KB Correct answer: answer = 5
25 Correct 1 ms 1900 KB Correct answer: answer = 41
26 Incorrect 1 ms 1900 KB Wrong answer: output = 3000000000000020942, expected = 71923
27 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 1 ms 1900 KB Correct answer: answer = 4
3 Correct 1 ms 1900 KB Correct answer: answer = 4
4 Correct 1 ms 1900 KB Correct answer: answer = 12
5 Correct 1 ms 1920 KB Correct answer: answer = 52
6 Correct 1 ms 1900 KB Correct answer: answer = 210
7 Correct 1 ms 1900 KB Correct answer: answer = 88
8 Correct 1 ms 1900 KB Correct answer: answer = 7696
9 Correct 1 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 1 ms 1900 KB Correct answer: answer = 49
13 Correct 1 ms 1900 KB Correct answer: answer = 151
14 Correct 1 ms 1900 KB Correct answer: answer = 7550
15 Correct 1 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 1 ms 1900 KB Correct answer: answer = 624
20 Correct 1 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 1 ms 1900 KB Correct answer: answer = 1
24 Correct 1 ms 1900 KB Correct answer: answer = 5
25 Correct 1 ms 1900 KB Correct answer: answer = 41
26 Incorrect 1 ms 1900 KB Wrong answer: output = 3000000000000020942, expected = 71923
27 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 1 ms 1900 KB Correct answer: answer = 4
3 Correct 1 ms 1900 KB Correct answer: answer = 4
4 Correct 1 ms 1900 KB Correct answer: answer = 12
5 Correct 1 ms 1920 KB Correct answer: answer = 52
6 Correct 1 ms 1900 KB Correct answer: answer = 210
7 Correct 1 ms 1900 KB Correct answer: answer = 88
8 Correct 1 ms 1900 KB Correct answer: answer = 7696
9 Correct 1 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 1 ms 1900 KB Correct answer: answer = 49
13 Correct 1 ms 1900 KB Correct answer: answer = 151
14 Correct 1 ms 1900 KB Correct answer: answer = 7550
15 Correct 1 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 1 ms 1900 KB Correct answer: answer = 624
20 Correct 1 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 1 ms 1900 KB Correct answer: answer = 1
24 Correct 1 ms 1900 KB Correct answer: answer = 5
25 Correct 1 ms 1900 KB Correct answer: answer = 41
26 Incorrect 1 ms 1900 KB Wrong answer: output = 3000000000000020942, expected = 71923
27 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 1 ms 1900 KB Correct answer: answer = 4
3 Correct 1 ms 1900 KB Correct answer: answer = 4
4 Correct 1 ms 1900 KB Correct answer: answer = 12
5 Correct 1 ms 1920 KB Correct answer: answer = 52
6 Correct 1 ms 1900 KB Correct answer: answer = 210
7 Correct 1 ms 1900 KB Correct answer: answer = 88
8 Correct 1 ms 1900 KB Correct answer: answer = 7696
9 Correct 1 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 1 ms 1900 KB Correct answer: answer = 49
13 Correct 1 ms 1900 KB Correct answer: answer = 151
14 Correct 1 ms 1900 KB Correct answer: answer = 7550
15 Correct 1 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 1 ms 1900 KB Correct answer: answer = 624
20 Correct 1 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 1 ms 1900 KB Correct answer: answer = 1
24 Correct 1 ms 1900 KB Correct answer: answer = 5
25 Correct 1 ms 1900 KB Correct answer: answer = 41
26 Incorrect 1 ms 1900 KB Wrong answer: output = 3000000000000020942, expected = 71923
27 Halted 0 ms 0 KB -