제출 #1196875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196875		dosts	말 (IOI15_horses)	C++20	17 / 100	439 ms	56064 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#pragma GCC target("lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " << 
using namespace std;
const int inf = 1e9+6;
const int LIM = 2e5+1,MOD = 1e9+7;

int mult(int x,int y) {
	return ((x%MOD)*(y%MOD))%MOD;
}

int expo(int x,int y) {
	if (!y) return 1;
	int e = expo(x,y/2);
	e = mult(e,e);
	if (y&1) e= mult(e,x);
	return e;
}

int divide(int x,int y) {
	return mult(x,expo(y,MOD-2));
}

struct FT {
	int n;
	vi bit;

	FT(){}
	FT(int nn) {
		n = nn;
		bit.assign(n+1,1);
	}

	void upd(int p,int v,int old) {
		int prd = divide(v,old);
		put(p,prd);
	}
	void put(int p,int v) {
		for (int i = p;i<=n;i+=i&-i) bit[i] = mult(bit[i],v);
	}

	int get(int p) {
		int ans = 1;
		for (int i = p;i>0;i-=i&-i) ans = mult(ans,bit[i]);
		return ans;
	}
} ft;


struct ST {
	vi t;
	ST(){}
	ST(int nn) {
		t.assign(4*nn+1,0);
	}

	void update(int node,int l,int r,int p,int v) {
		if (l == r) {
			t[node] = v;
			return;
		}
		int m = (l+r) >> 1;
		if (p <= m) update(2*node,l,m,p,v);
		else update(2*node+1,m+1,r,p,v);
		t[node] = max(t[2*node],t[2*node+1]);
	}

	int query(int node,int l,int r,int L,int R) {
		if (l > R || r < L) return 0;
		if (l >= L && r <= R) return t[node];
		int m = (l+r) >> 1;
		return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
	}
} st;

set<int> checker;
vi xx,yy;
int nn;

int calc() {
	auto it = checker.end();
	int prd = 1;
	while (it != checker.begin()) {
		it = prev(it);
		prd*=xx[*it];
		if (prd > inf) {
			it = next(it);
			break;
		}
	}
	vector<pii> v;
	prd = 1;
	int ans = 0;
	int mx = -1;
	for (;it != checker.end();it = next(it)) {
		prd *= xx[*it];
		int mxv = st.query(1,1,nn,*it,nn);
		if (prd*mxv > mx) {
			mx = prd*mxv;
			ans = mult(ft.get(*it),mxv);
		}
	}
	return ans;
}

int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
	checker.insert(1);
	nn = N;
	xx.resize(N+1),yy.resize(N+1);
	for (int i=1;i<=N;i++) xx[i] = X[i-1],yy[i] = Y[i-1];
	ft = FT(N);
	st = ST(N);
	for (int i = 1;i<=N;i++) {
		if (xx[i] > 1) checker.insert(i);
		ft.upd(i,xx[i],1);
		st.update(1,1,N,i,yy[i]);	
	}
	return calc();
}

int32_t updateX(int32_t pos, int32_t val) {	
	pos++;
	if (xx[pos] > 1) checker.erase(pos);
	if (val > 1) checker.insert(pos);
	checker.insert(1);
	ft.upd(pos,val,xx[pos]);
	xx[pos] = val;
	return calc();
}

int32_t updateY(int32_t pos, int32_t val) {
	pos++;
	st.update(1,1,nn,pos,val);
	yy[pos] = val;
	return calc();
}

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