제출 #1321594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1321594		nagorn_ph	말 (IOI15_horses)	C++20	17 / 100	863 ms	60872 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
#define int long long

using namespace std;

const int mod = 1e9 + 7;
const int N = 5e5 + 5;

int n;
int x[N], y[N];
bool inside[N];

struct segtree {
	struct node {
		int val;
		bool exceed;
		node() : val(0), exceed(0) {}
	};
	node seg[4 * N];
	node create(){
		node newnode;
		newnode.val = 1;
		newnode.exceed = 0;
		return newnode;
	}
	node merge(node l, node r){
		node newnode = create();
		newnode.exceed = (l.exceed || r.exceed);
		newnode.val = (l.val * r.val) % mod;
		if ((l.val * r.val) >= mod) newnode.exceed = true;
		return newnode;
	}
	void build(int l, int r, int i){
		if (l == r) return seg[i].val = x[l], void();
		int mid = (l + r) / 2;
		build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
		seg[i] = merge(seg[2 * i], seg[2 * i + 1]);
	}
	void update(int l, int r, int i, int idx, int val){
		if (l == r) return seg[i].val = val, void();
		int mid = (l + r) / 2;
		if (idx <= mid) update(l, mid, 2 * i, idx, val);
		else update(mid + 1, r, 2 * i + 1, idx, val);
		seg[i] = merge(seg[2 * i], seg[2 * i + 1]);
	}
	node query(int l, int r, int i, int ll, int rr){
		if (l >= ll && r <= rr) return seg[i];
		if (r < ll || l > rr) return create();
		int mid = (l + r) / 2;
		return merge(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
	}
} seg;

struct indexmaintain {
	int seg[4 * N];
	void build(int l, int r, int i){
		if (l == r) return seg[i] = (x[l] > 1), void();
		int mid = (l + r) / 2;
		build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
		seg[i] = seg[2 * i] + seg[2 * i + 1];
	}
	void update(int l, int r, int i, int idx, int val){
		if (l == r) return seg[i] = (val > 1), void();
		int mid = (l + r) / 2;
		if (idx <= mid) update(l, mid, 2 * i, idx, val);
		else update(mid + 1, r, 2 * i + 1, idx, val);
		seg[i] = seg[2 * i] + seg[2 * i + 1];
	}
	int query(int l, int r, int i, int k){
		if (l == r) return l;
		int mid = (l + r) / 2;
		if (seg[2 * i + 1] >= k) return query(mid + 1, r, 2 * i + 1, k);
		else return query(l, mid, 2 * i, k - seg[2 * i + 1]);
	}
} indices;

struct mxseg{
	int seg[4 * N];
	void build(int l, int r, int i){
		if (l == r) return seg[i] = y[l], void();
		int mid = (l + r) / 2;
		build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
		seg[i] = max(seg[2 * i], seg[2 * i + 1]);
	}
	void update(int l, int r, int i, int idx, int val){
		if (l == r) return seg[i] = val, void();
		int mid = (l + r) / 2;
		if (idx <= mid) update(l, mid, 2 * i, idx, val);
		else update(mid + 1, r, 2 * i + 1, idx, val);
		seg[i] = max(seg[2 * i], seg[2 * i + 1]);
	}
	int query(int l, int r, int i, int ll, int rr){
		if (l >= ll && r <= rr) return seg[i];
		if (r < ll || l > rr) return 0;
		int mid = (l + r) / 2;
		return max(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
	}
} mxx;

int query(){
	int st = 1, exact = indices.seg[1];
	for (int i = 1; i <= indices.seg[1]; i++) {
		int idx = indices.query(1, n, 1, i);
		// cout << i << ": " << idx << ": " << seg.query(1, n, 1, idx, n).exceed << "\n";
		if (seg.query(1, n, 1, idx, n).exceed) {
			st = idx + 1;
			exact = i - 1;
			break;
		}
	}
	int mx = 0;
	int prev = n + 1;
	for (int i = 1; i <= exact; i++) {
		int idx = indices.query(1, n, 1, i);
		mx = max(mx, seg.query(1, n, 1, st, idx).val * mxx.query(1, n, 1, idx, prev - 1));
		prev = idx;
	}
	mx = max(mx, mxx.query(1, n, 1, st, prev - 1));
	return ((seg.query(1, n, 1, 1, st - 1).val * (mx % mod)) % mod);
}

int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
	n = N;
	for (int i = 0; i < n; i++) x[i + 1] = X[i];
	for (int i = 0; i < n; i++) y[i + 1] = Y[i];
	y[0] = 1;
	seg.build(1, n, 1);
	indices.build(1, n, 1);
	mxx.build(1, n, 1);
	return query();
}

int32_t updateX(int32_t pos, int32_t val) {	
	++pos;
	seg.update(1, n, 1, pos, val);
	indices.update(1, n, 1, pos, val);
	return query();
}

int32_t updateY(int32_t pos, int32_t val) {
	++pos;
	y[pos] = val;
	mxx.update(1, n, 1, pos, val);
	return query();
}

// int32_t main(){
// 	int32_t n; cin >> n;
// 	int32_t x[n], y[n];
// 	for (int i = 0; i < n; i++) cin >> x[i];
// 	for (int i = 0; i < n; i++) cin >> y[i];
// 	cout << init(n, x, y) << "\n";
// 	int32_t m; cin >> m;
// 	while (m--) {
// 		int t; cin >> t;
// 		int pos, val; cin >> pos >> val;
// 		if (t == 1) cout << updateX(pos, val) << "\n";
// 		else cout << updateY(pos, val) << "\n";
// 	}
// }

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23