Submission #223722

#	Time	Username	Problem	Language	Result	Execution time	Memory
223722		cki86201	Sushi (JOI16_sushi)	C++17	100 / 100	6251 ms	125588 KiB

sushi

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

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

const int BS = 400, MXN = 400040;
int N, Q, X[MXN];

struct Block {
	int V[BS+1], len;
	priority_queue <int> pq;
	priority_queue <int, vector<int>, greater<> > qs;
	void Init(int A[], int L) {
		for(int i=0;i<L;i++) {
			V[i] = A[i];
			pq.push(V[i]);
		}
		len = L;
	}
	int Push(int x) {
		qs.push(x);
		pq.push(x);
		int r = pq.top(); pq.pop();
		return r;
	}
	void Resolve() {
		rep(i, len) {
			qs.push(V[i]);
			V[i] = qs.top(); qs.pop();
		}
		while(!qs.empty()) qs.pop();
	}
	int query(int l, int r, int x) {
		if(l == 0 && r == len - 1) {
			return Push(x);
		}
		else {
			if(!qs.empty()) Resolve();
			for(int i=l;i<=r;i++) {
				if(V[i] > x) swap(V[i], x);
			}
			while(!pq.empty()) pq.pop();
			rep(i, len) pq.push(V[i]);
			return x;
		}
	}
} F[MXN/BS+3];

void Init() {
	for(int i=0;i*BS+1<=N;i++) {
		int lv = i * BS + 1, rv = min(N, (i+1) * BS);
		F[i].Init(X + lv, rv - lv + 1);
	}
}

int Query(int s, int t, int p) {
	if(s > t) {
		return Query(1, t, Query(s, N, p));
	}
	auto get_bn = [](int x) { return (x-1) / BS; };
	int sb = get_bn(s), st = get_bn(t);
	for(int i=sb;i<=st;i++) {
		int lv = i * BS + 1;
		int l = max(s, i*BS+1);
		int r = min(t, (i+1)*BS);
		p = F[i].query(l - lv, r - lv, p);
	}
	return p;
}

int main() {
	scanf("%d%d", &N, &Q);
	for(int i=1;i<=N;i++) scanf("%d", X + i);
	Init();
	for(int i=1;i<=Q;i++) {
		int s, t, p;
		scanf("%d%d%d", &s, &t, &p);
		printf("%d\n", Query(s, t, p));
	}
	return 0;
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:81: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:82:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%d", X + i);
                        ~~~~~^~~~~~~~~~~~~
sushi.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &s, &t, &p);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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