Submission #55979

#	Time	Username	Problem	Language	Result	Execution time	Memory
55979		khsoo01	Sushi (JOI16_sushi)	C++11	100 / 100	8977 ms	97696 KiB

sushi

#include<bits/stdc++.h>
using namespace std;

const int N = 400005, BS = 500;

int n, q, bc, a[N];

struct bucket {
	vector<int> v;
	priority_queue<int> p, d;
	void ins (int V) {
		v.push_back(V);
		p.push(V);
	}
	void relax () {
		for(int i=0;i<(int)v.size();i++) {
			d.push(-v[i]);
			v[i] = -d.top();
			d.pop();
		}
		while(!d.empty()) {
			d.pop();
		}
	}
	int put (int X) {
		p.push(X);
		d.push(-X);
		int T = p.top();
		p.pop();
		return T;
	}
	int naive (int S, int E, int X) {
		if(E == -1) E = (int)v.size() - 1;
		relax();
		for(int i=S;i<=E;i++) {
			if(v[i] > X) swap(v[i], X);
		}
		while(!p.empty()) {
			p.pop();
		}
		for(int i=0;i<(int)v.size();i++) {
			p.push(v[i]);
		}
		return X;
	}
} b[N/BS+5];

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=0;i<n;i++) {
		scanf("%d",&a[i]);
		b[i/BS].ins(a[i]);
	}
	bc = (n-1)/BS + 1;
	while(q--) {
		int A, B, C;
		scanf("%d%d%d",&A,&B,&C);
		A--;
		B--;
		if(A <= B && A/BS == B/BS) {
			printf("%d\n",b[A/BS].naive(A%BS, B%BS, C));
		}
		else {
			C = b[A/BS].naive(A%BS, -1, C);
			for(int i=A/BS;;) {
				i = (i+1) % bc;
				if(i == B/BS) break;
				else C = b[i].put(C);
			}
			printf("%d\n",b[B/BS].naive(0, B%BS, C));
		}
	}
}

Compilation message (stderr)

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