Submission #1083177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083177		kes0716	Sushi (JOI16_sushi)	C++17	100 / 100	8003 ms	56192 KiB

sushi

#include <bits/stdc++.h>
#define TEST2
#define RAND2
using namespace std;
const int MAXN = 401557, buc = 1500, BUCN = MAXN/buc;
int n, a[MAXN];
priority_queue<int, vector<int>, greater<int> > lazy[BUCN];
multiset<int> st[BUCN];	//i-th bucket: [i*buc, (i+1)*buc)
void dolazy(int v){
	int li = v*buc, ri = min((v+1)*buc, n) - 1, k;
	#ifdef TEST
	printf("v=%d lazy.size=%d\n", v, lazy[v].size());
	#endif
	for(k=li; k<=ri; k++){
		lazy[v].push(a[k]);
		a[k] = lazy[v].top();
		lazy[v].pop();
	}
	while(!lazy[v].empty())
		lazy[v].pop();
}
int go(int v, int l, int r, int val){
	//printf("v=%d l=%d r=%d\n", v, l, r);
	int now = val;
	int k;
	for(k=l; k<=r; k++){
		#ifdef TEST
		printf("k=%d a[k]=%d\n", k, a[k]);
		#endif
		//printf("k=%d false=%d\n", k, st[v].find(a[k]) == st[v].end());
		if(a[k] > now){
			st[v].erase(st[v].find(a[k]));
			st[v].insert(now);
			swap(a[k], now);
		}
	}
	return now;
}
int main(){
	int q, i, l, r, val;
	scanf("%d %d", &n, &q);
	int m = (n+buc-1)/buc;
	srand(time(NULL));
	for(i=0; i<n; i++){
		#ifdef RAND
		a[i] = rand() % 50;
		printf("%d ", a[i]);
		#endif
		#ifndef RAND
		scanf("%d", &a[i]);
		#endif
		st[i/buc].insert(a[i]);
	}
	//printf("\n");
	while(q--){
		#ifndef RAND
		scanf("%d %d %d", &l, &r, &val);
		#endif
		#ifdef RAND
		l = rand() % n + 1;
		r = rand() % n + 1;
		val = rand() % 40;
		printf("%d %d %d\n", l, r, val);
		#endif
		l--;
		r--;
		int lb = l/buc, rb = r/buc;
		if(l > r){
			rb += m;
		}
		if(lb == rb){
			dolazy(lb);
			printf("%d\n", go(lb, l, r, val));
			continue;
		}
		dolazy(lb);
		val = go(lb, l, min((lb+1)*buc, n) - 1, val);
		//printf("lb=%d rb=%d\n", lb, rb);
		for(int t=lb+1; t<rb; t++){
			i = t%m;
			lazy[i].push(val);
			st[i].insert(val);
			val = *(--st[i].end());
			st[i].erase(--st[i].end());
		}
		dolazy(rb%m);
		printf("%d\n", go(rb%m, rb%m*buc, r, val));
		#ifdef TEST
		for(i=0; i<m; i++){
			printf("bucket %d: ", i);
			for(int v: st[i])
				printf("%d ", v);
			printf("\n");
		}
		#endif
	}
	return 0;
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
sushi.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d %d %d", &l, &r, &val);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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