Submission #134845

#	Time	Username	Problem	Language	Result	Execution time	Memory
134845		sebinkim	Sushi (JOI16_sushi)	C++14	100 / 100	3072 ms	76340 KiB

sushi

#include <bits/stdc++.h>
 
using namespace std;
 
int sz = 700;
 
int A[404040], H[404040];
int B[404040], 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(;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);
		}
	}
	
	return 0;
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.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);
  ~~~~~^~~~~~~~~~~~~~~~
sushi.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A+i);
   ~~~~~^~~~~~~~~~~
sushi.cpp:48: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: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80