oj.uz

Submission #139873

# Submission time Handle Problem Language Result Execution time Memory
139873 2019-08-01T15:11:50 Z SirCeness Aliens (IOI16_aliens) C++14
4 / 100
 2 ms 380 KB 
#include "aliens.h"
#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000000000009
#define mod 1000000007
#define ppair(x) "(" << x.first << ", " << x.second << ") "
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

vector<pair<int, int> > arr;

ll sq(int a, int b){
	if (a < b) return 0;
	return (ll)(a-b+1)*(ll)(a-b+1);
}

ll getcost(int a, int b){
	return sq(arr[b].x, arr[a].y) - sq(arr[a].x, arr[a].y) - sq(arr[b].x, arr[b].y) + sq(arr[a].x, arr[b].y);
}

int cmp(const pair<int, int>& lhs, const pair<int, int>& rhs){
	if (lhs.second == rhs.second) return lhs.first > rhs.first;
	return lhs.second < rhs.second;
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
	vector<pair<int, int> > ekle1;
	for (int i = 0; i < n; i++) if (r[i] >= c[i]) ekle1.pb(mp(r[i], c[i]));
	else ekle1.pb(mp(c[i], r[i]));
	
	sort(ekle1.begin(), ekle1.end(), cmp);
	arr.pb(ekle1[0]);
	//cout << ppair(ekle1[0]) << " ";
	for (int i = 1; i < n; i++){
		//cout << ppair(ekle1[i]) << " ";
		if (ekle1[i].second == arr.back().second) continue;
		if (ekle1[i].first <= arr.back().first) continue;
		arr.pb(ekle1[i]);
	}
	//cout << endl;
	
	//for (int i = 0; i < arr.size(); i++) cout << ppair(arr[i]) << endl;
	
	ll ans = 0;
	for (int i = 0; i < arr.size(); i++){
		ans += sq(arr[i].x, arr[i].y);
		if (i+1 != arr.size()) ans -= sq(arr[i].x, arr[i+1].y);
	}
	
	set<pair<ll, int> > st;
	for (int i = 0; i < arr.size()-1; i++){
		ll cost = getcost(i, i+1);
		st.insert(mp(cost, i));
	}
	
	vector<int> bef(arr.size());
	for (int i = 1; i < arr.size(); i++) bef[i] = i-1;
	bef[0] = -1;
	vector<int> nex(arr.size());
	for (int i = 0; i < arr.size()-1; i++) nex[i] = i+1;
	nex[arr.size()-1] = -1;
	
	
	for (int q = 0; q < (int)arr.size()-k; q++){
		//for (pair<ll, int> eleman: st) cout << ppair(eleman) << " "; cout << endl;
		int i = st.begin() -> second;
		ans += st.begin() -> first;
		int b = bef[i];
		int nx = nex[nex[i]];
		st.erase(st.begin());
		if (b != -1){
			ll costb = getcost(b, i);
			int tmp = st.size();
			st.erase(st.find(mp(costb, b)));
			if (tmp-1 != st.size()) assert(0);
		}
		if (nx != -1){
			ll costn = getcost(nex[i], nx);
			int tmp = st.size();
			st.erase(st.find(mp(costn, nex[i])));
			if (tmp-1 != st.size()) assert(0);
		}
		
		arr[i].x = arr[nex[i]].x;
		
		nex[i] = nx;
		if (nx != -1) bef[nx] = i;
		
		if (b != -1) st.insert(mp(getcost(b, i), b));
		if (nx != -1) st.insert(mp(getcost(i, nx), i));
		
	}
	
	
	
    return ans;
}

Compilation message

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); i++){
                  ~~^~~~~~~~~~~~
aliens.cpp:57:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i+1 != arr.size()) ans -= sq(arr[i].x, arr[i+1].y);
       ~~~~^~~~~~~~~~~~~
aliens.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size()-1; i++){
                  ~~^~~~~~~~~~~~~~
aliens.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < arr.size(); i++) bef[i] = i-1;
                  ~~^~~~~~~~~~~~
aliens.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size()-1; i++) nex[i] = i+1;
                  ~~^~~~~~~~~~~~~~
aliens.cpp:85:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (tmp-1 != st.size()) assert(0);
        ~~~~~~^~~~~~~~~~~~
aliens.cpp:91:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (tmp-1 != st.size()) assert(0);
        ~~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Correct answer: answer = 1
2 Correct 2 ms 256 KB Correct answer: answer = 4
3 Correct 2 ms 256 KB Correct answer: answer = 1
4 Correct 2 ms 376 KB Correct answer: answer = 5
5 Correct 2 ms 376 KB Correct answer: answer = 41
6 Correct 2 ms 376 KB Correct answer: answer = 71923
7 Incorrect 2 ms 376 KB Wrong answer: output = 80476, expected = 77137
8 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 256 KB Correct answer: answer = 4
4 Correct 2 ms 380 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 380 KB Correct answer: answer = 210
7 Correct 2 ms 256 KB Correct answer: answer = 88
8 Correct 2 ms 256 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 256 KB Correct answer: answer = 2374
11 Correct 2 ms 376 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 256 KB Correct answer: answer = 151
14 Correct 2 ms 376 KB Correct answer: answer = 7550
15 Correct 2 ms 256 KB Correct answer: answer = 7220
16 Correct 2 ms 256 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 276 KB Correct answer: answer = 10000
19 Correct 2 ms 256 KB Correct answer: answer = 624
20 Correct 2 ms 256 KB Correct answer: answer = 10000
21 Correct 2 ms 256 KB Correct answer: answer = 1
22 Correct 2 ms 256 KB Correct answer: answer = 4
23 Correct 2 ms 256 KB Correct answer: answer = 1
24 Correct 2 ms 376 KB Correct answer: answer = 5
25 Correct 2 ms 376 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Incorrect 2 ms 376 KB Wrong answer: output = 80476, expected = 77137
28 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 256 KB Correct answer: answer = 4
4 Correct 2 ms 380 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 380 KB Correct answer: answer = 210
7 Correct 2 ms 256 KB Correct answer: answer = 88
8 Correct 2 ms 256 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 256 KB Correct answer: answer = 2374
11 Correct 2 ms 376 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 256 KB Correct answer: answer = 151
14 Correct 2 ms 376 KB Correct answer: answer = 7550
15 Correct 2 ms 256 KB Correct answer: answer = 7220
16 Correct 2 ms 256 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 276 KB Correct answer: answer = 10000
19 Correct 2 ms 256 KB Correct answer: answer = 624
20 Correct 2 ms 256 KB Correct answer: answer = 10000
21 Correct 2 ms 256 KB Correct answer: answer = 1
22 Correct 2 ms 256 KB Correct answer: answer = 4
23 Correct 2 ms 256 KB Correct answer: answer = 1
24 Correct 2 ms 376 KB Correct answer: answer = 5
25 Correct 2 ms 376 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Incorrect 2 ms 376 KB Wrong answer: output = 80476, expected = 77137
28 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 256 KB Correct answer: answer = 4
4 Correct 2 ms 380 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 380 KB Correct answer: answer = 210
7 Correct 2 ms 256 KB Correct answer: answer = 88
8 Correct 2 ms 256 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 256 KB Correct answer: answer = 2374
11 Correct 2 ms 376 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 256 KB Correct answer: answer = 151
14 Correct 2 ms 376 KB Correct answer: answer = 7550
15 Correct 2 ms 256 KB Correct answer: answer = 7220
16 Correct 2 ms 256 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 276 KB Correct answer: answer = 10000
19 Correct 2 ms 256 KB Correct answer: answer = 624
20 Correct 2 ms 256 KB Correct answer: answer = 10000
21 Correct 2 ms 256 KB Correct answer: answer = 1
22 Correct 2 ms 256 KB Correct answer: answer = 4
23 Correct 2 ms 256 KB Correct answer: answer = 1
24 Correct 2 ms 376 KB Correct answer: answer = 5
25 Correct 2 ms 376 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Incorrect 2 ms 376 KB Wrong answer: output = 80476, expected = 77137
28 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 256 KB Correct answer: answer = 4
4 Correct 2 ms 380 KB Correct answer: answer = 12
5 Correct 2 ms 376 KB Correct answer: answer = 52
6 Correct 2 ms 380 KB Correct answer: answer = 210
7 Correct 2 ms 256 KB Correct answer: answer = 88
8 Correct 2 ms 256 KB Correct answer: answer = 7696
9 Correct 2 ms 376 KB Correct answer: answer = 1
10 Correct 2 ms 256 KB Correct answer: answer = 2374
11 Correct 2 ms 376 KB Correct answer: answer = 9502
12 Correct 2 ms 376 KB Correct answer: answer = 49
13 Correct 2 ms 256 KB Correct answer: answer = 151
14 Correct 2 ms 376 KB Correct answer: answer = 7550
15 Correct 2 ms 256 KB Correct answer: answer = 7220
16 Correct 2 ms 256 KB Correct answer: answer = 7550
17 Correct 2 ms 376 KB Correct answer: answer = 10000
18 Correct 2 ms 276 KB Correct answer: answer = 10000
19 Correct 2 ms 256 KB Correct answer: answer = 624
20 Correct 2 ms 256 KB Correct answer: answer = 10000
21 Correct 2 ms 256 KB Correct answer: answer = 1
22 Correct 2 ms 256 KB Correct answer: answer = 4
23 Correct 2 ms 256 KB Correct answer: answer = 1
24 Correct 2 ms 376 KB Correct answer: answer = 5
25 Correct 2 ms 376 KB Correct answer: answer = 41
26 Correct 2 ms 376 KB Correct answer: answer = 71923
27 Incorrect 2 ms 376 KB Wrong answer: output = 80476, expected = 77137
28 Halted 0 ms 0 KB -