oj.uz

Submission #55098

# Submission time Handle Problem Language Result Execution time Memory
55098 2018-07-06T04:46:48 Z ainta(#1558) Sushi (JOI16_sushi) C++11
0 / 100
 499 ms 3816 KB 
#include<cstdio>
#include<algorithm>
#include<queue>
#define BB 10
using namespace std;
int n, Q;
struct point {
	int P[1<<BB], SZ;
	int U[1<<BB], UC;
	priority_queue<int>PQ;
	void init() {
		int i;
		for (i = UC - 1; i >= 0; i--) {
			P[U[i]] = PQ.top();
			PQ.pop();
		}
	}
	void Make() {
		int i, Mx = -1;
		UC = 0;
		while (!PQ.empty())PQ.pop();
		for (i = 0; i < SZ; i++) {
			if (Mx < P[i]) {
				Mx = P[i];
				U[UC++] = i;
				PQ.push(P[i]);
			}
		}
	}
	int Go(int x) {
		PQ.push(x);
		int ret = PQ.top();
		PQ.pop();
		return ret;
	}
}w[(400000>>BB)+2];
int Do(int b, int e, int x) {
	for (int i = (b >> BB); i <= (e >> BB); i++) {
		int bb = (i << BB), ee = min(((i + 1) << BB) - 1, n - 1);
		if (b <= bb && bb <= e) {
			x = w[i].Go(x);
		}
		else{
			w[i].init();
			bb = max(b, bb)&((1 << BB) - 1);
			ee = min(e, ee)&((1 << BB) - 1);
			for (int j = bb; j <= ee; j++) {
				if (w[i].P[j] > x) {
					swap(w[i].P[j], x);
				}
			}
			w[i].Make();
		}
	}
	return x;
}
int main() {
	int i, b, e, c;
	scanf("%d%d", &n, &Q);
	for (i = 0; i < n; i++) {
		scanf("%d", &w[i>>BB].P[i&((1<<BB)-1)]);
		w[i >> BB].SZ++;
	}
	for (i = 0; i <= ((n - 1) >> BB); i++)w[i].Make();
	while (Q--) {
		scanf("%d%d%d", &b, &e, &c);
		b--, e--;
		if (b > e) {
			printf("%d\n",Do(0, e, Do(b, n - 1, c)));
		}
		else {
			printf("%d\n", Do(b, e, c));
		}
	}
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
telegraph.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i>>BB].P[i&((1<<BB)-1)]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
telegraph.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &b, &e, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 80.0

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