Submission #414660

#	Time	Username	Problem	Language	Result	Execution time	Memory
414660		ja_kingy	Horses (IOI15_horses)	C++14	100 / 100	426 ms	53340 KiB

horses

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

set<int> xge2;
const int mxN = 5e5, SZ = 1<<19, MOD = 1e9+7;
struct ST {
	int sz;
	vector<int> mul, mx;
	ST (int sz) : sz(sz), mul(2*sz, 1), mx(2*sz){}
	int qmx(int l, int r) {
		int res = 0;
		for (l += sz, r += sz; l < r; l/=2, r/=2) {
			if (l&1) res = max(res, mx[l++]);
			if (r&1) res = max(res, mx[--r]);
		}
		return res;
	}
	int qmul(int l, int r) {
		int res = 1;
		for (l += sz, r += sz; l < r; l/=2, r/=2) {
			if (l&1) res = (long long)res*mul[l++]%MOD;
			if (r&1) res = (long long)res*mul[--r]%MOD;
		}
		return res;
	}
	void umul(int x, int v) {
		x += sz;
		mul[x] = v;
		for (; x /= 2;) mul[x] = (long long)mul[x*2]*mul[x*2+1]%MOD;
	}
	void umx(int x, int v) {
		x += sz;
		mx[x] = v;
		for (; x /= 2;) mx[x] = max(mx[x*2], mx[x*2+1]);
	}
} st(SZ);
int n, x[mxN], y[mxN];
int ans() {
	long long val = 0, pos = n;
    for (auto it = xge2.end(); it != xge2.begin();) {
		it--;
		val = x[*it] * max((long long)st.qmx(*it, pos), val);
		pos = *it;
		if (val > MOD) break;
	}
	val = max(val, (long long)st.mx[1]);
	return val%MOD*st.qmul(0, pos)%MOD;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < N; ++i) {
		if (X[i] >= 2) xge2.insert(i);
		st.umul(i, X[i]);
		st.umx(i, Y[i]);
	}
	copy(X, X+N, x);
	copy(Y, Y+N, y);
	return ans();
}

int updateX(int pos, int val) {
	if (val == 1) xge2.erase(pos);
	else xge2.insert(pos);
	st.umul(pos, x[pos]=val);
	return ans();
}

int updateY(int pos, int val) {
	st.umx(pos, y[pos]=val);
	return ans();
}

Compilation message (stderr)

horses.cpp: In constructor 'ST::ST(int)':
horses.cpp:10:10: warning: declaration of 'sz' shadows a member of 'ST' [-Wshadow]
   10 |  ST (int sz) : sz(sz), mul(2*sz, 1), mx(2*sz){}
      |      ~~~~^~
horses.cpp:8:6: note: shadowed declaration is here
    8 |  int sz;
      |      ^~
horses.cpp: In constructor 'ST::ST(int)':
horses.cpp:10:10: warning: declaration of 'sz' shadows a member of 'ST' [-Wshadow]
   10 |  ST (int sz) : sz(sz), mul(2*sz, 1), mx(2*sz){}
      |      ~~~~^~
horses.cpp:8:6: note: shadowed declaration is here
    8 |  int sz;
      |      ^~
horses.cpp: In constructor 'ST::ST(int)':
horses.cpp:10:10: warning: declaration of 'sz' shadows a member of 'ST' [-Wshadow]
   10 |  ST (int sz) : sz(sz), mul(2*sz, 1), mx(2*sz){}
      |      ~~~~^~
horses.cpp:8:6: note: shadowed declaration is here
    8 |  int sz;
      |      ^~
horses.cpp: In member function 'int ST::qmul(int, int)':
horses.cpp:22:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |    if (l&1) res = (long long)res*mul[l++]%MOD;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:23:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   23 |    if (r&1) res = (long long)res*mul[--r]%MOD;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In member function 'void ST::umul(int, int)':
horses.cpp:30:58: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   30 |   for (; x /= 2;) mul[x] = (long long)mul[x*2]*mul[x*2+1]%MOD;
      |                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int ans()':
horses.cpp:43:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   43 |   val = x[*it] * max((long long)st.qmx(*it, pos), val);
      |                                             ^~~
horses.cpp:48:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   48 |  return val%MOD*st.qmul(0, pos)%MOD;
      |                            ^~~
horses.cpp:48:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   48 |  return val%MOD*st.qmul(0, pos)%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~^~~~

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