oj.uz

Submission #55929

# Submission time Handle Problem Language Result Execution time Memory
55929 2018-07-09T07:46:09 Z 김세빈(#1563) Sushi (JOI16_sushi) C++11
0 / 100
 371 ms 4228 KB 
#include <bits/stdc++.h>

using namespace std;

int sz = 700;

int A[404040], H[404040];
int B[1010], L[1010], R[1010];
priority_queue <int, vector<int>, greater<int>> Q[1010];
int n, k;

void spread(int x)
{
	if(Q[x].empty()) return;
	
	int i;
	
	for(i=L[x];i<=R[x];i++){
		if(A[i] > Q[x].top()){
			Q[x].push(A[i]);
			A[i] = Q[x].top(); Q[x].pop();
		}
	}
	
	for(;!Q[x].empty();) Q[x].pop();
}

int main()
{
	int q, i, a, b, c, x, y;
	
	scanf("%d%d", &n, &q);
	
	for(i=0;i<n;i++){
		scanf("%d", A+i);
		H[i] = A[i]; B[i] = i/sz;
		if(i % sz == 0) L[i/sz] = i;
		R[i/sz] = i;
	}
	
	k = (n - 1) / sz + 1;
	
	for(i=0;i<k;i++){
		make_heap(H + L[i], H + R[i] + 1);
	}
/*		
	for(i=0;i<n;i++) printf("%d ",A[i]);
	printf("\n");
	for(i=0;i<n;i++) printf("%d ",H[i]);
	printf("\n");
*/	
	for(;q--;){
		scanf("%d%d%d", &a, &b, &c);
		a --, b --;
		x = B[a], y = B[b];
		
		if(x == y){
			if(a <= b){
				spread(x);
				for(i=a;i<=b;i++){
					if(A[i] > c) swap(A[i], c);
				}
				
				for(i=L[x];i<=R[x];i++) H[i] = A[i];
				make_heap(H + L[x], H + R[x] + 1);
				
				printf("%d\n", c);
			}
			else{
				spread(x);
				for(i=a;i<=R[x];i++){
					if(A[i] > c) swap(A[i], c);
				}
				x = (x + 1) % k;
				
				for(;x!=y;x=(x+1)%k){
					if(H[L[x]] > c){
						Q[x].push(c);
						pop_heap(H + L[x], H + R[x] + 1);
						swap(c, H[R[x]]);
						push_heap(H + L[x], H + R[x] + 1);
					}
				}
				
				for(i=L[x];i<=b;i++){
					if(A[i] > c) swap(A[i], c);
				}
				
				for(i=L[x];i<=R[x];i++) H[i] = A[i];
				make_heap(H + L[x], H + R[x] + 1);
				
				printf("%d\n", c);
			}
		}
		else{
			if(L[x] != a){
				spread(x);
				
				for(i=a;i<=R[x];i++){
					if(A[i] > c) swap(A[i], c);
				}
				
				for(i=L[x];i<=R[x];i++) H[i] = A[i];
				make_heap(H + L[x], H + R[x] + 1);
				
				x = (x + 1) % k;
			}
			
			
			for(;x!=y;x=(x+1)%k){
				if(H[L[x]] > c){
					Q[x].push(c);
					pop_heap(H + L[x], H + R[x] + 1);
					swap(c, H[R[x]]);
					push_heap(H + L[x], H + R[x] + 1);
				}
			}
					
			spread(y);
			for(i=L[y];i<=b;i++){
				if(A[i] > c) swap(A[i], c);
			}
			
			for(i=L[y];i<=R[y];i++) H[i] = A[i];
			make_heap(H + L[y], H + R[y] + 1);

			printf("%d\n", c);
		}
/*		
		for(i=0;i<n;i++) printf("%d ",A[i]);
		printf("\n");
		for(i=0;i<n;i++) printf("%d ",H[i]);
		printf("\n");
*/	}
	
	return 0;
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:32: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:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A+i);
   ~~~~~^~~~~~~~~~~
telegraph.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -