Submission #1217414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217414		_asunaa	Index (COCI21_index)	C++20	110 / 110	1975 ms	226004 KiB

index

#include <bits/stdc++.h>
using namespace std;
long long i, j, l, r, mid, p, q, k, t, n, m, a, b, c, d, ans, cnt, res, kmy[200005], kmy4[200005], st[800005];
pair <long long, long long> kmy2[200005];
struct aa{
	long long id;
	long long ll;
	long long rr;
	long long qa;
	long long qb;
	long long qc;
};

aa query[200005];
vector <aa> kmy3[200005];

const long long mod = 999993143;
string s;
bool check;
void build (long long id, long long l, long long r){
	if (l == r){
		st[id] = kmy4[l];
		return;
	}
	long long mid = (l + r) >> 1;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	st[id] = st[id * 2] + st[id * 2 + 1];
}

void update (long long id, long long l, long long r, long long i, long long val){
	if (i < l || i > r){
		return;
	}
	if (l == r){
		st[id] += val;
		return;
	}
	long long mid = (l + r) >> 1;
	update(id * 2, l, mid, i, val);
	update(id * 2 + 1, mid + 1, r, i, val);
	st[id] = st[id * 2] + st[id * 2 + 1];
}

long long get (long long id, long long l, long long r, long long u, long long v){
	if (v < l || u > r){
		return 0;
	}
	if (u <= l && r <= v){
		return st[id];
	}
	long long mid = (l + r) >> 1;
	return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}

bool cmp (pair <long long, long long> a, pair <long long, long long> b){
	return a.first > b.first;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for (i = 1; i <= n; i += 1){
		cin >> kmy[i];
		kmy4[i] = 0;
	}
	for (i = 1; i <= q; i += 1){
		cin >> a >> b;
		query[i] = {i, 1, n, a, b, -1};
	}
	for (i = 1; i <= n; i += 1){
		kmy2[i] = make_pair(kmy[i], i);
	}
	sort(kmy2 + 1, kmy2 + n + 1, cmp);
	for (d = 1; d <= 18; d += 1){
		build(1, 1, n);
		for (i = 1; i <= n; i += 1){
			kmy3[i].clear();
		}
		for (i = 1; i <= q; i += 1){
			kmy3[(query[i].ll + query[i].rr) >> 1ll].push_back(query[i]);
		}
		p = 1;
		for (i = n; i >= 1; i -= 1){
			while (p <= n){
//				cout << p << "a\n";
				if (kmy2[p].first >= i){
					update(1, 1, n, kmy2[p].second, 1);
					p += 1;
				}
				else{
					break;
				}
			}
			for (j = 0; j < kmy3[i].size(); j += 1){
				if (query[kmy3[i][j].id].ll > query[kmy3[i][j].id].rr){
					continue;
				}
				if (get(1, 1, n, query[kmy3[i][j].id].qa, query[kmy3[i][j].id].qb) >= i){
					query[kmy3[i][j].id].qc = max(query[kmy3[i][j].id].qc, i);
					query[kmy3[i][j].id].ll = i + 1;
				}
				else{
					query[kmy3[i][j].id].rr = i - 1;
				}
			}
		}
	}
	for (i = 1; i <= q; i += 1){
		if (query[i].qa == query[i].qb){
			cout << 1 << "\n";
		}
		else{
			cout << query[i].qc << "\n";
		}
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50