제출 #1321604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1321604		nagorn_ph	말 (IOI15_horses)	C++20	컴파일 에러	0 ms	0 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;
			exact = i;
			break;
		}
	}
	if (indices.seg[1] == 0) return mxx.query(1, n, 1, 1, n);
	long double mx = 0;
	long double prod = 1.0;
	int num = 1, prodmod = 1;
	for (int i = exact; i >= 1; i--) {
		int idx = indices.query(1, n, 1, i);
		prod *= x[idx];
		prodmod = (prodmod * x[idx]) % mod;
		int nxt = (i == 1 ? n + 1 : indices.query(1, n, 1, i - 1));
		int mxy = mxx.query(1, n, 1, idx, nxt - 1);
		if (prod * mxy > mx) {
			mx = prod * mxy;
			num = (prodmod * mxy) % mod;
		}
	}
	int answer = ((seg.query(1, n, 1, 1, st - 1).val * num) % mod);
	return answer;
}

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;
	x[pos] = val;
	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";
	}
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccjck2aN.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKPgS0D.o:horses.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status