Submission #387316

#	Time	Username	Problem	Language	Result	Execution time	Memory
387316		aarr	Horses (IOI15_horses)	C++14	17 / 100	1557 ms	54892 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 500 * 1000 + 5, mod = 1000 * 1000 * 1000 + 7;
int n;

long long seg1[N * 4];
int seg2[N * 4];
set <int, greater<int> > s;
int a[N], b[N];

void update1(int p, int val, int id = 1, int s = 0, int e = n) {
	if (e - s == 1) {
		seg1[id] = val;
		return;
	}
	int md = (s + e) / 2;
	if (p < md) {
		update1(p, val, id * 2, s, md);
	}
	else {
		update1(p, val, id * 2 + 1, md, e);
	}
	seg1[id] = (seg1[id * 2] * seg1[id * 2 + 1]) % mod;
}

void update2(int p, int val, int id = 1, int s = 0, int e = n) {
	if (e - s == 1) {
		seg2[id] = val;
		return;
	}
	int md = (s + e) / 2;
	if (p < md) {
		update2(p, val, id * 2, s, md);
	}
	else {
		update2(p, val, id * 2 + 1, md, e);
	}
	seg2[id] = max(seg2[id * 2], seg2[id * 2 + 1]);
}

long long get1(int l, int r, int id = 1, int s = 0, int e = n) {
	if (r <= s || e <= l) {
		return 1;
	}
	if (l <= s && e <= r) {
		return seg1[id];
	}
	int md = (s + e) / 2;
	return (get1(l, r, id * 2, s, md) * get1(l, r, id * 2 + 1, md, e)) % mod;
}

int get2(int l, int r, int id = 1, int s = 0, int e = n) {
	if (r <= s || e <= l) {
		return 0;
	}
	if (l <= s && e <= r) {
		return seg2[id];
	}
	int md = (s + e) / 2;
	return max(get2(l, r, id * 2, s, md), get2(l, r, id * 2 + 1, md, e));
}

int getans() {
	long long mp = 1;
	long long ans = 0;
	long long u = 1;
	int mx = 0, mfor = 0;
	long long mmp = 1;
	set <int, greater <int> > :: iterator it = s.begin();
	while (true) {
		int k = *it;
		if (k == -1) {
		//	ans = max(ans, get2(0, n));
			break;
		}
		else {
		//	cout << "75 " << k << endl;
			int t = get2(k, n);
			long long s = get1(0, k + 1);
			u = s;
			s *= t;
			s %= mod;
		//	cout << "78 " << k << " " << t << " " << s << " " << mp << endl;
			if (mp * mx < t * mmp) {
				mmp = mp;
				mx = t;
				mfor = k;
			}
			mp *= a[k];
		}
		if (mp > mod) {
			break;
		}
		it++;
	}
	ans = get1(0, mfor + 1) * mx;
	ans %= mod;
//	cout << "74 " << mfor << " " << mx << " " << ans << endl;
	return ans;
}

int init(int nn, int X[], int Y[]) {
	n = nn;
	fill(seg1, seg1 + n * 4, 1);
	for (int i = 0; i < n; i++) {
		a[i] = X[i];
		b[i] = Y[i];
		update1(i, a[i]);
		update2(i, b[i]);
		if (a[i] > 1) {
			s.insert(i);
		}
	}
	s.insert(-1);
	s.insert(0);
//	cout << "72 " << get1(0, 3) << " " << get2(0, 3) << endl;
	return getans();
}

int updateX(int pos, int val) {	
	update1(pos, val);
	if (val > 1) {
		s.insert(pos);
	}
	else if(pos != 0) {
		s.erase(pos);
	}
	a[pos] = val;
	return getans();
}

int updateY(int pos, int val) {
	update2(pos, val);
	a[pos] = val;
	return getans();
}

Compilation message (stderr)

horses.cpp: In function 'void update1(int, int, int, int, int)':
horses.cpp:13:62: warning: declaration of 's' shadows a global declaration [-Wshadow]
   13 | void update1(int p, int val, int id = 1, int s = 0, int e = n) {
      |                                                              ^
horses.cpp:10:26: note: shadowed declaration is here
   10 | set <int, greater<int> > s;
      |                          ^
horses.cpp: In function 'void update2(int, int, int, int, int)':
horses.cpp:28:62: warning: declaration of 's' shadows a global declaration [-Wshadow]
   28 | void update2(int p, int val, int id = 1, int s = 0, int e = n) {
      |                                                              ^
horses.cpp:10:26: note: shadowed declaration is here
   10 | set <int, greater<int> > s;
      |                          ^
horses.cpp: In function 'long long int get1(int, int, int, int, int)':
horses.cpp:43:62: warning: declaration of 's' shadows a global declaration [-Wshadow]
   43 | long long get1(int l, int r, int id = 1, int s = 0, int e = n) {
      |                                                              ^
horses.cpp:10:26: note: shadowed declaration is here
   10 | set <int, greater<int> > s;
      |                          ^
horses.cpp: In function 'int get2(int, int, int, int, int)':
horses.cpp:54:56: warning: declaration of 's' shadows a global declaration [-Wshadow]
   54 | int get2(int l, int r, int id = 1, int s = 0, int e = n) {
      |                                                        ^
horses.cpp:10:26: note: shadowed declaration is here
   10 | set <int, greater<int> > s;
      |                          ^
horses.cpp: In function 'int getans()':
horses.cpp:81:14: warning: declaration of 's' shadows a global declaration [-Wshadow]
   81 |    long long s = get1(0, k + 1);
      |              ^
horses.cpp:10:26: note: shadowed declaration is here
   10 | set <int, greater<int> > s;
      |                          ^
horses.cpp:101:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |  return ans;
      |         ^~~
horses.cpp:68:12: warning: variable 'u' set but not used [-Wunused-but-set-variable]
   68 |  long long u = 1;
      |            ^

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