Submission #795973

#	Time	Username	Problem	Language	Result	Execution time	Memory
795973		acatmeowmeow	Horses (IOI15_horses)	C++11	0 / 100	971 ms	64528 KiB

horses

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

using namespace std;

#define int long long 

const int NMAX = 5e5, modulo = 1e9 + 7;
int n, x[NMAX + 5], y[NMAX + 5], tree[4*NMAX + 5], tree2[4*NMAX + 5];
set<pair<int, int>> pos;

int combine(int a, int b) { return y[a] > y[b] ? a : b; }

void update(int v, int tl, int tr, int k) {
	if(tl == tr) tree[v] = k;
	else {
		int tm = (tl + tr)/2;
		if(k <= tm) update(v*2, tl, tm, k);
		else update(v*2 + 1, tm + 1, tr, k);
		tree[v] = combine(tree[v*2], tree[v*2 + 1]);
	}
}

int query(int v, int tl, int tr, int l, int r) {
	if(l >r) return 0;
	else if (tl == l && tr == r) return tree[v];
	else {
		int tm = (tl + tr)/2;
		return combine(query(v*2, tl, tm, l, min(tm, r)), query(v*2 + 1, tm + 1, tr, max(l, tm + 1), r));
	}
}

void update2(int v, int tl, int tr, int k, int x) {
	if (tl == tr) tree2[v] = x;
	else {
		int tm = (tl + tr)/2;
		if (k <= tm) update2(v*2, tl, tm, k, x);
		else update2(v*2 + 1, tm + 1, tr, k, x);
		tree2[v] = (tree2[v*2]*tree2[v*2 + 1]) % modulo;
	}
}

int query2(int v, int tl, int tr, int l, int r) {
	if (l > r) return 1;
	else if (tl == l&& tr == r) return tree2[v];
	else {
		int tm = (tl+ tr)/2;
		return (query2(v*2, tl, tm, l, min(tm, r))*query2(v*2 + 1, tm + 1, tr, max(l, tm + 1), r)) % modulo;
	}
}

void merge(int index) {
	if (x[index] != 1) { pos.insert({index, index}); return; }
	auto rig = pos.upper_bound({index, -1e9}), lef = rig; lef--;
	bool l1 = x[index - 1] == 1, r1 = x[index + 1] == 1;
	pair<int, int> lp = *lef, rp = *rig;
	if (lp.second + 1 == index && index + 1 == rp.first && l1 && r1) pos.erase(lef), pos.erase(rig), pos.insert({lp.first, rp.second});
	else if (lp.second + 1 == index && l1) pos.erase(lef), pos.insert({lp.first, index});
	else if (index + 1 == rp.first && r1) pos.erase(rig), pos.insert({index, rp.second});
	else pos.insert({index, index});
}

void split(int index) {
	auto it = pos.upper_bound({index, -1e9}); it--;
	pair<int, int> p = *it;
	pos.erase(it);
	if (p.first < index) pos.insert({p.first, index - 1});
	if (index < p.second) pos.insert({index + 1, p.second});
}

int compute() {
	auto it = pos.end(); it--, it--;
	vector<int> res;
	for (int cnt = 60; cnt && it != pos.begin(); it--, cnt--) {
		int l = it->first, r = it->second;
		int maxY = query(1, 1, n, l, r);
		res.push_back(maxY);
	}
	int mx = 0;
	for (int i = 1; i < res.size(); i++) {
		int cur = y[res[mx]];
		for (int j = mx; j <= i && cur <= y[res[i]]; j++) cur *= x[res[j]];
		if (cur <= y[res[i]]) mx = i;
	}
	//for (int i = 0; i < res.size(); i++) cout << res[i] << " ";
	//cout << '\n';
	//for (auto&x : pos) cout << x.first << " " << x.second << '\n';
	return (query2(1, 1, n, 1, res[mx])*y[res[mx]]) % modulo;	
}

signed init(signed N, signed X[], signed Y[]) {
	n = N;
	for (int i = 1; i <= n; i++) x[i] = X[i - 1], y[i] = Y[i - 1];
	pos.insert({-1, -1}), pos.insert({1e9, 1e9});
	for (int i = 1; i <= n; i++) merge(i);
	for (int i = 1; i <= n; i++) update(1, 1, n, i), update2(1, 1, n, i, x[i]);
	return compute();
}

signed updateX(signed pos, signed val) {	
	pos++;
	if (x[pos] == val) return compute();
	split(pos);
	x[pos] = val;
	update2(1, 1, n, pos, x[pos]);
	merge(pos);
	return compute();
}

signed updateY(signed pos, signed val) {
	pos++;
	y[pos] = val;
	update(1, 1, n, pos);
	return compute();
}

/*signed main() {
	//_inputFile = fopen("horses.in", "rb");
	//_outputFile = fopen("horses.out", "w");

	signed N;
	cin >> N;

	signed *X = (signed*)malloc(sizeof(signed)*(unsigned)N);
	signed *Y = (signed*)malloc(sizeof(signed)*(unsigned)N);

	for (int i = 0; i < N; i++) {
		cin >> X[i];
	}

	for (int i = 0; i < N; i++) {
		cin >> Y[i];
	}

	//fprintf(_outputFile,"%d\n",init(N,X,Y));
	cout << init(N, X, Y) << '\n';

	signed M;
	cin >> M;

	for (int i = 0; i < M; i++) {
		signed type; cin >> type;
		signed pos; cin >> pos;
		signed val; cin >> val;

		if (type == 1) {
			//fprintf(_outputFile,"%d\n",updateX(pos,val));
			cout << updateX(pos, val) << '\n';
		} else if (type == 2) {
			//fprintf(_outputFile,"%d\n",updateY(pos,val));
			cout << updateY(pos, val) << '\n';
		}
	}

	return 0;
}*/

Compilation message (stderr)

horses.cpp: In function 'void update2(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:33:48: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   33 | void update2(int v, int tl, int tr, int k, int x) {
      |                                                ^
horses.cpp:9:8: note: shadowed declaration is here
    9 | int n, x[NMAX + 5], y[NMAX + 5], tree[4*NMAX + 5], tree2[4*NMAX + 5];
      |        ^
horses.cpp: In function 'long long int compute()':
horses.cpp:80:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 1; i < res.size(); i++) {
      |                  ~~^~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:97:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   97 |  return compute();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:100:23: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  100 | signed updateX(signed pos, signed val) {
      |                ~~~~~~~^~~
horses.cpp:10:21: note: shadowed declaration is here
   10 | set<pair<int, int>> pos;
      |                     ^~~
horses.cpp:102:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |  if (x[pos] == val) return compute();
      |                            ~~~~~~~^~
horses.cpp:107:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |  return compute();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:110:23: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  110 | signed updateY(signed pos, signed val) {
      |                ~~~~~~~^~~
horses.cpp:10:21: note: shadowed declaration is here
   10 | set<pair<int, int>> pos;
      |                     ^~~
horses.cpp:114:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |  return compute();
      |         ~~~~~~~^~

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