Submission #202438

#	Time	Username	Problem	Language	Result	Execution time	Memory
202438		ho94949	Sushi (JOI16_sushi)	C++17	100 / 100	9053 ms	83064 KiB

sushi

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 400000;
const int BUCKET = 625;
const int BUCKET_CNT = 640;
int arr[MAXN];
priority_queue<int> pq[BUCKET_CNT];
priority_queue<int, vector<int>, greater<int> > lazy[BUCKET_CNT];
int N, Q;
void init()
{
	for(int i=0; i<BUCKET_CNT; ++i)
	{
		for(int j=0; j<BUCKET; ++j)
		{
			if(i*BUCKET+j >= N) return;
			pq[i].push(arr[i*BUCKET+j]);
		}
	}
}
void bucket_fixup(int bucket_idx)
{
	for(int i=bucket_idx*BUCKET; i<min(N, (bucket_idx+1)*BUCKET); ++i)
	{
		lazy[bucket_idx].push(arr[i]);
		arr[i] = lazy[bucket_idx].top();
		lazy[bucket_idx].pop();
	}
	while(!lazy[bucket_idx].empty()) lazy[bucket_idx].pop();
}
int naive(int l, int r, int v)
{
	int bucket_idx = l/BUCKET;
	bucket_fixup(l/BUCKET);
	for(int i=l; i<=r; ++i)
		if(arr[i] > v)
			swap(arr[i], v);
	while(!pq[bucket_idx].empty()) pq[bucket_idx].pop();
	for(int i=bucket_idx*BUCKET; i<min(N, (bucket_idx+1)*BUCKET); ++i)
		pq[bucket_idx].push(arr[i]);
	return v;
}
int Query(int l, int r, int v)
{
	int l_bucket = l/BUCKET, r_bucket = r/BUCKET;
	if(l_bucket == r_bucket)
		return naive(l, r, v);
	
	v = naive(l, l_bucket*BUCKET + BUCKET-1, v);
	for(int i=l_bucket+1; i<=r_bucket-1; ++i)
	{
		pq[i].push(v);
		lazy[i].push(v);
		v = pq[i].top(); pq[i].pop();
	}
	v = naive(r_bucket*BUCKET, r, v);
	return v;
}
int main()
{
	scanf("%d%d", &N, &Q);
	for(int i=0; i<N; ++i)
		scanf("%d", &arr[i]);
	init();
	vector<tuple<int, int, int> > queries;
	for(int i=0; i<Q; ++i)
	{
		int a, b, c; scanf("%d%d%d", &a, &b, &c);
		--a; --b;
		if(a<=b)
		{
			printf("%d\n", Query(a, b, c));
		}
		else
		{
			int q = Query(a, N-1, c);
			printf("%d\n", Query(0, b, q));
		}
	}
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80