oj.uz

Submission #150069

# Submission time Handle Problem Language Result Execution time Memory
150069 2019-09-01T07:39:13 Z GucciBelt(#3697, PeppaPig, win11905, DodgeBallMan) Crosses on the Grid (FXCUP4_cross) C++17
8 / 100
 116 ms 5736 KB 
#include <bits/stdc++.h>
#include "cross.h"
#define long long long 
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int INF = 1e9+1;

int n;
long ans;

long SelectCross(int K, vector<int> I, vector<int> O) {
	n = I.size();
	vector<pii> vec;
	for(int i = 0; i < n; ++i) vec.emplace_back(O[i], I[i]);
	sort(vec.begin(), vec.end(), [&](const pii &a, const pii &b) {
		if(a.x != b.x) return a.x > b.x;
		return a.y < b.y;
	});
	priority_queue<int> Q;
	for(auto x : vec) {
		// cerr << x.x << ' ' << x.y << endl;

		if(Q.size() == K) Q.pop();
		if(Q.size() == K-1) {
			int v = min(x.y, Q.empty() ? INF : Q.top());
			ans = max(ans, 1ll * x.x * x.x - 1ll * (x.x - v) * (x.x - v));
		}
		Q.emplace(x.y);
	}
	return ans;
}

Compilation message

cross.cpp: In function 'long long int SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(Q.size() == K) Q.pop();
      ~~~~~~~~~^~~~
cross.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(Q.size() == K-1) {
      ~~~~~~~~~^~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 380 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 12 ms 768 KB Output is correct
6 Correct 112 ms 5736 KB Output is correct
7 Correct 110 ms 5736 KB Output is correct
8 Correct 116 ms 5484 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 380 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 12 ms 768 KB Output is correct
6 Correct 112 ms 5736 KB Output is correct
7 Correct 110 ms 5736 KB Output is correct
8 Correct 116 ms 5484 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Incorrect 5 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 380 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 12 ms 768 KB Output is correct
6 Correct 112 ms 5736 KB Output is correct
7 Correct 110 ms 5736 KB Output is correct
8 Correct 116 ms 5484 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Incorrect 5 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -