oj.uz

Submission #54357

# Submission time Handle Problem Language Result Execution time Memory
54357 2018-07-03T08:15:57 Z 창조론자(#2048) Sails (IOI07_sails) C++11
5 / 100
 70 ms 3180 KB 
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
struct xy { long long x, y; }a[121212];
bool sort_x(xy a, xy b) { if (a.x != b.x)return a.x > b.x; return a.y < b.y; }
long long max(long long a, long long b) { if (a < b)return b; return a; }
long long H[121212], mh, n;
long long F(long long x) {
	long long i, j, now = 0, num = 0, res = 0;
	for (i = 1; i <= mh; i++)H[i] = 0;
	priority_queue<int>Q;
	for (i = mh; i >= 1; i--) {
		while (now < n && a[now].x == i)Q.push(a[now++].y);
		num += H[i];
		res += num*(num - 1) / 2;
		for (j = num + 1; j <= x; j++) {
			if (Q.empty())break;
			long long now = Q.top(); Q.pop();
			if (i < now)return 0;
			H[i - now]--; num++;
			res += j - 1;
		}
	}
	if (!Q.empty())return 0;
	return res;
}
int main() {
	long long i, j; scanf("%lld", &n);
	for (i = 0; i < n; i++) scanf("%lld%lld", &a[i].x, &a[i].y), mh = max(mh, a[i].x);;
	sort(a, a + n, sort_x);
	long long s = 1, e = n, ans;
	while (s <= e) {
		long long m = (s + e) / 2;
		long long f = F(m);
		if (f)e = m - 1, ans = f;
		else s = m + 1;
	}
	printf("%lld", ans);
	return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:29:15: warning: unused variable 'j' [-Wunused-variable]
  long long i, j; scanf("%lld", &n);
               ^
sails.cpp:29:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long i, j; scanf("%lld", &n);
                  ~~~~~^~~~~~~~~~~~
sails.cpp:30:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < n; i++) scanf("%lld%lld", &a[i].x, &a[i].y), mh = max(mh, a[i].x);;
                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 476 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 476 KB Output is correct
2 Incorrect 2 ms 572 KB Output isn't correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 572 KB Output is correct
2 Incorrect 2 ms 572 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1360 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 1900 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 2568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 3180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 3180 KB Output isn't correct
2 Halted 0 ms 0 KB -