Submission #795429

#	Time	Username	Problem	Language	Result	Execution time	Memory
795429		Josia	Horses (IOI15_horses)	C++17	100 / 100	823 ms	84128 KiB

horses

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

using namespace std;

#define ll long long
#define int long long

constexpr ll mod = 1e9+7;

struct seg {
	// vector<int> tree;
	array<signed, 2000000> tree;

	void init(int n) {
		// tree.assign(n*4, 0);
	}

	void update(int v, int rl, int rr, int pos, int x) {
		if (rl == rr) {
			tree[v] = x;
			return;
		}

		int rm = (rl + rr)/2;

		if (pos <= rm) update(v*2, rl, rm, pos, x);
		else update(v*2+1, rm+1, rr, pos, x);

		tree[v] = max(tree[v*2], tree[v*2+1]);
	}

	int query(int v, int rl, int rr, int ql, int qr) {
		if (ql > qr) return 0;

		if (rl == ql && rr == qr) return tree[v];

		int rm = (rl + rr)/2;

		return max(query(v*2, rl, rm, ql, min(qr, rm)), query(v*2+1, rm+1, rr, max(ql, rm+1), qr));
	}
};

struct segY {
	vector<pair<int, int>> tree;

	void init(int n) {
		tree.assign(n*4, {0, 0});
	}

	void update(int v, int rl, int rr, int pos, int x) {
		if (rl == rr) {
			tree[v] = {x, pos};
			return;
		}

		int rm = (rl + rr)/2;

		if (pos <= rm) update(v*2, rl, rm, pos, x);
		else update(v*2+1, rm+1, rr, pos, x);

		tree[v] = max(tree[v*2], tree[v*2+1]);
	}

	pair<int, int> query(int v, int rl, int rr, int ql, int qr) {
		if (ql > qr) return {0, -1};

		if (rl == ql && rr == qr) return tree[v];

		int rm = (rl + rr)/2;

		return max(query(v*2, rl, rm, ql, min(qr, rm)), query(v*2+1, rm+1, rr, max(ql, rm+1), qr));
	}
};

ll mult(ll a, ll b) {
	int res = a*b;
	if (res >= mod) res%=mod;
	return res;
}

struct seg2 {
	vector<ll> tree;

	void init(int n) {
		tree.assign(n*4, 0);
	}

	void update(int v, int rl, int rr, int pos, int x) {
		if (rl == rr) {
			tree[v] = x;
			return;
		}

		int rm = (rl + rr)/2;

		if (pos <= rm) update(v*2, rl, rm, pos, x);
		else update(v*2+1, rm+1, rr, pos, x);

		tree[v] = mult(tree[v*2], tree[v*2+1]);
	}

	ll query(int v, int rl, int rr, int ql, int qr) {
		if (ql > qr) return 1;

		if (rl == ql && rr == qr) return tree[v];

		int rm = (rl + rr)/2;

		return mult(query(v*2, rl, rm, ql, min(qr, rm)), query(v*2+1, rm+1, rr, max(ql, rm+1), qr));
	}
};



struct rightestNonZero {
	// vector<int> tree;
	array<signed, 2000000> tree;

	void init(int n) {
		// tree.assign(n*4, 0);
	}

	void update(int v, int rl, int rr, int pos, int x) {
		if (rl == rr) {
			tree[v] = x?pos:-1;
			return;
		}

		int rm = (rl + rr)/2;

		if (pos <= rm) update(v*2, rl, rm, pos, x);
		else update(v*2+1, rm+1, rr, pos, x);

		tree[v] = max(tree[v*2], tree[v*2+1]);
	}

	int query(int v, int rl, int rr, int ql, int qr) {
		if (ql > qr) return 0;

		if (rl == ql && rr == qr) return tree[v];

		int rm = (rl + rr)/2;

		return max(query(v*2, rl, rm, ql, min(qr, rm)), query(v*2+1, rm+1, rr, max(ql, rm+1), qr));
	}
};

struct leftestNonZero {
	// vector<int> tree;
	array<signed, 2000000> tree;

	void init(int n) {
		// tree.assign(n*4, 0);
	}

	void update(int v, int rl, int rr, int pos, int x) {
		if (rl == rr) {
			tree[v] = x?pos:1e9;
			return;
		}

		int rm = (rl + rr)/2;

		if (pos <= rm) update(v*2, rl, rm, pos, x);
		else update(v*2+1, rm+1, rr, pos, x);

		tree[v] = min(tree[v*2], tree[v*2+1]);
	}

	int query(int v, int rl, int rr, int ql, int qr) {
		if (ql > qr) return 0;

		if (rl == ql && rr == qr) return tree[v];

		int rm = (rl + rr)/2;

		return min(query(v*2, rl, rm, ql, min(qr, rm)), query(v*2+1, rm+1, rr, max(ql, rm+1), qr));
	}
};



seg tree;
segY treeY;
seg2 tree2;
leftestNonZero lnz;
rightestNonZero rnz;
int N;
vector<ll> X, Y;

struct getSol {
	int sol = 0;

	int BS(int pos) {
		if (pos == 0) return -1;

		int res = rnz.query(1, 0, N-1, 0, pos-1);

		if (res==-1) return 0;
		return res;

		int l = 0, r = pos-1;
		while (l<r) {
			int m = (l+r+1)/2;
			if (tree.query(1, 0, N-1, m, pos-1) > 1) {
				l = m;
			} else {
				r = m-1;
			}
		}

		return l;
	}

	int BSinv(int pos) {
		if (pos == N-1) return N-1;

		int res = lnz.query(1, 0, N-1, pos+1, N-1);

		return res;


		int l = pos+1, r = N-1;
		while (l<r) {
			int m = (l+r+1)/2;
			if (tree.query(1, 0, N-1, pos+1, m) > 1) {
				r = m-1;
			} else {
				l = m;
			}
		}

		return l;
	}


	int findInd() {
		int currInd = N-1;
		ll currProd = 1;
		for (int i = N-1; i>=0; i = BS(i)) {
			auto bestSell = treeY.query(1, 0, N-1, i, N-1);
			if (currProd*Y[currInd] <= bestSell.first) {currInd = bestSell.second; currProd=1;}

			currProd *= X[i];
			if (currProd*Y[currInd] > 1e9) break;
		}
		return currInd;
	}


	getSol() {
		int ind = findInd();

		sol = (tree2.query(1, 0, N-1, 0, ind) * Y[ind])%mod;
	}
};




signed init(signed _N, signed _X[], signed _Y[]) {
	N = _N;
	X.resize(N);
	Y.resize(N);
	for (int i = 0; i<N; i++) X[i] = _X[i];
	for (int i = 0; i<N; i++) Y[i] = _Y[i];

	tree.init(N);
	treeY.init(N);
	tree2.init(N);

	for (int i = 0; i<N; i++) {
		lnz.update(1, 0, N-1, i, X[i]>1);
		rnz.update(1, 0, N-1, i, X[i]>1);
		tree.update(1, 0, N-1, i, X[i]);
		treeY.update(1, 0, N-1, i, Y[i]);
		tree2.update(1, 0, N-1, i, X[i]);
	}
	return getSol().sol;
}

signed updateX(signed pos, signed val) {
	tree.update(1, 0, N-1, pos, val);
	tree2.update(1, 0, N-1, pos, val);

	lnz.update(1, 0, N-1, pos, val>1);
	rnz.update(1, 0, N-1, pos, val>1);

	X[pos] = val;

	return getSol().sol;
}

signed updateY(signed pos, signed val) {
	treeY.update(1, 0, N-1, pos, val);
	Y[pos] = val;

	return getSol().sol;
}

Compilation message (stderr)

horses.cpp: In member function 'void seg::init(long long int)':
horses.cpp:15:16: warning: unused parameter 'n' [-Wunused-parameter]
   15 |  void init(int n) {
      |                ^
horses.cpp: In member function 'void seg::update(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:21:14: warning: conversion from 'long long int' to 'std::array<int, 2000000>::value_type' {aka 'int'} may change value [-Wconversion]
   21 |    tree[v] = x;
      |              ^
horses.cpp: In member function 'void rightestNonZero::init(long long int)':
horses.cpp:120:16: warning: unused parameter 'n' [-Wunused-parameter]
  120 |  void init(int n) {
      |                ^
horses.cpp: In member function 'void rightestNonZero::update(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:126:15: warning: conversion from 'long long int' to 'std::array<int, 2000000>::value_type' {aka 'int'} may change value [-Wconversion]
  126 |    tree[v] = x?pos:-1;
      |              ~^~~~~~~
horses.cpp: In member function 'void leftestNonZero::init(long long int)':
horses.cpp:153:16: warning: unused parameter 'n' [-Wunused-parameter]
  153 |  void init(int n) {
      |                ^
horses.cpp: In member function 'void leftestNonZero::update(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:159:16: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  159 |    tree[v] = x?pos:1e9;
      |                ^~~
horses.cpp:159:15: warning: conversion from 'double' to 'std::array<int, 2000000>::value_type' {aka 'int'} may change value [-Wfloat-conversion]
  159 |    tree[v] = x?pos:1e9;
      |              ~^~~~~~~~
horses.cpp: In member function 'long long int getSol::findInd()':
horses.cpp:246:16: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  246 |    if (currProd*Y[currInd] > 1e9) break;
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:280:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  280 |  return getSol().sol;
      |         ~~~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:292:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  292 |  return getSol().sol;
      |         ~~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:299:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  299 |  return getSol().sol;
      |         ~~~~~~~~~^~~

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