Submission #1281564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281564		nathlol2	Horses (IOI15_horses)	C++20	0 / 100	272 ms	115152 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 5;
const ll MOD = 1e9 + 7;
vector<ll> x(N), y(N);
int n;
struct lazyseg{
	pair<long double, int> seg[4*N];
	long double lazy[4*N];
	lazyseg(){
		for(int i = 0;i<4*N;i++){
			lazy[i] = 0;
		}
	}
	void push(int nd, int l, int r){
		if(lazy[nd] != 0){
			seg[nd].first += lazy[nd];
			if(l != r){
				lazy[nd * 2] += lazy[nd];
				lazy[nd * 2 + 1] += lazy[nd];
			}
			lazy[nd] = 0;
		}
	}
	void build(int nd, int l, int r){
		if(l == r){
			seg[nd] = {-4e18, l};
			return;
		}
		int md = (l + r) / 2;
		build(nd * 2, l, md);
		build(nd * 2 + 1, md + 1, r);
	}
	void upd(int nd, int l, int r, int ql, int qr, long double v){
		push(nd, l, r);
		if(r < ql || l > qr) return;
		if(ql <= l && r <= qr){
			lazy[nd] += v;
			push(nd, l, r);
			return;
		}
		int md = (l + r) / 2;
		upd(2 * nd, l, md, ql, qr, v);
		upd(2 * nd + 1, md + 1, r, ql, qr, v);
		seg[nd] = max(seg[nd * 2], seg[nd * 2 + 1]);
	}
	int qry(){
		return seg[1].second;
	}
}s;
struct segtree{
	ll seg[4*N];
	void build(int nd, int l, int r){
		if(l == r) return seg[nd] = x[l - 1], void();
		int md = (l + r) / 2;
		build(nd * 2, l, md);
		build(nd * 2 + 1, md + 1, r);
		seg[nd] = seg[nd * 2] * seg[nd * 2 + 1];
		seg[nd] %= MOD;
	}
	void upd(int nd, int l, int r, int pos, int v){
		if(l == r) return seg[nd] = v, void();
		int md = (l + r) / 2;
		if(pos <= md) upd(nd * 2, l, md, pos, v);
		else upd(nd * 2 + 1, md + 1, r, pos, v);
		seg[nd] = seg[nd * 2] * seg[nd * 2 + 1];
		seg[nd] %= MOD;
	}
	ll qry(int nd, int l, int r, int ql, int qr){
		if(r < ql || l > qr) return 1;
		if(ql <= l && r <= qr) return seg[nd];
		int md = (l + r) / 2;
		return (qry(nd * 2, l, md, ql, qr) * qry(nd * 2, md + 1, r, ql, qr)) % MOD;
	}
}pf;
int init(int NN, int X[], int Y[]) {
	n = NN;
	for(int i = 0;i<n;i++) x[i] = X[i], y[i] = Y[i];
	long double c = log(x[0]);
	s.build(1, 1, n);
	s.upd(1, 1, n, 1, 1, c);
	pf.build(1, 1, n);
	for(int i = 1;i<n;i++){
		c += log(x[i]);
		s.upd(1, 1, n, i + 1, i + 1, c + log(y[i]));
	}
	int idx = s.qry();
	return (pf.qry(1, 1, n, 1, idx) * y[idx - 1]) % MOD;
}

int updateX(int pos, int val) {
	s.upd(1, 1, n, pos + 1, n, -log(x[pos]));
	x[pos] = val;
	s.upd(1, 1, n, pos + 1, n, log(x[pos]));
	pf.upd(1, 1, n, pos + 1, val);
	int idx = s.qry();
	return (pf.qry(1, 1, n, 1, idx) * y[idx - 1]) % MOD;
}

int updateY(int pos, int val) {
	s.upd(1, 1, n, pos + 1, pos + 1, -log(y[pos]));
	y[pos] = val;
	s.upd(1, 1, n, pos + 1, pos + 1, log(y[pos]));
	int idx = s.qry();
	return (pf.qry(1, 1, n, 1, idx) * y[idx - 1]) % MOD;
}

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