Submission #1049860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049860		TAhmed33	Horses (IOI15_horses)	C++98	57 / 100	1517 ms	114876 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
typedef long double ld;
int add (int a, int b) {
	a += b; if (a >= MOD) a -= MOD;
	return a;
}
int sub (int a, int b) {
	a -= b; if (a < 0) a += MOD;
	return a;
}
int mul (int a, int b) {
	return (a * 1ll * b) % MOD;
}
int power (int a, int b) {
	if (!b) return 1;
	int u = power(a, b >> 1);
	u = mul(u, u);
	if (b & 1) u = mul(u, a);
	return u;
}
int inv (int x) {
	return power(x, MOD - 2);
}
int x[MAXN], y[MAXN], n;
struct SegmentTree {
	pair <ld, int> tree[MAXN << 2];
	ld lazy[MAXN << 2];
	void init (int l, int r, int node) {
		lazy[node] = 0; tree[node] = {ld(0), l};
		if (l == r) {
			return;
		}
		init(l, mid, tl); init(mid + 1, r, tr);
	}
	void prop (int l, int r, int node) {
		if (l != r) {
			lazy[tl] += lazy[node];
			lazy[tr] += lazy[node];
		}
		tree[node].first += lazy[node];
		lazy[node] = 0;
	}
	void update (int l, int r, int a, int b, ld c, int node) {
		prop(l, r, node);
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			lazy[node] += c;
			prop(l, r, node);
			return;
		}
		update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr);
		tree[node] = max(tree[tl], tree[tr]);
	}
	pair <ld, int> get (int l, int r, int a, int b, int node) {
		prop(l, r, node);
		if (l > b || r < a) return {ld(0), n + 1};
		if (l >= a && r <= b) return tree[node];
		return max(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
	}
} cur;
struct SegmentTree2 {
	int tree[MAXN << 2], lazy[MAXN << 2];
	void init (int l, int r, int node) {
		tree[node] = 1; lazy[node] = 1;
		if (l == r) return;
		init(l, mid, tl); init(mid + 1, r, tr);
	}
	void prop (int l, int r, int node) {
		if (l != r) {
			lazy[tl] = mul(lazy[tl], lazy[node]);
			lazy[tr] = mul(lazy[tr], lazy[node]);
		}
		tree[node] = mul(tree[node], lazy[node]);
		lazy[node] = 1;
	}
	void update (int l, int r, int a, int b, int c, int node) {
		prop(l, r, node);
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			lazy[node] = mul(lazy[node], c);
			prop(l, r, node);
			return;
		}
		update(l, mid ,a, b, c, tl);
		update(mid + 1, r, a, b, c, tr);
	}
	int get (int l, int r, int a, int node) {
		prop(l, r, node);
		if (l == r) return tree[node];
		if (a <= mid) return get(l, mid, a, tl);
		else return get(mid + 1, r, a, tr);
	}
} cur2;
int ans () {
	auto z = cur.get(0, n - 1, 0, n - 1, 1);
	return cur2.get(0, n - 1, z.second, 1);
}
int init (int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; i++) {
		x[i] = X[i]; y[i] = Y[i];
	}
	cur.init(0, n - 1, 1);
	cur2.init(0, n - 1, 1);
	for (int i = 0; i < n; i++) {
		cur.update(0, n - 1, i, n - 1, log2(x[i]), 1);
		cur2.update(0, n - 1, i, n - 1, x[i], 1);
		cur.update(0, n - 1, i, i, log2(y[i]), 1);
		cur2.update(0, n - 1, i, i, y[i], 1);
	}
	return ans();
}

int updateX (int pos, int val) {	
	cur.update(0, n - 1, pos, n - 1, log2(val) - log2(x[pos]), 1);
	cur2.update(0, n - 1, pos, n - 1, mul(val, inv(x[pos])), 1);
	x[pos] = val;
	return ans();
}

int updateY (int pos, int val) {
	cur.update(0, n - 1, pos, pos, log2(val) - log2(y[pos]), 1);
	cur2.update(0, n - 1, pos, pos, mul(val, inv(y[pos])), 1);
	y[pos] = val;
	return ans();
}

Compilation message (stderr)

horses.cpp: In function 'int mul(int, int)':
horses.cpp:19:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |  return (a * 1ll * b) % MOD;
      |         ~~~~~~~~~~~~~~^~~~~

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