Submission #802297

#	Time	Username	Problem	Language	Result	Execution time	Memory
802297		jlallas384	Horses (IOI15_horses)	C++17	100 / 100	785 ms	84252 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;

vector<int> x, y;
int n;

struct tree{
	tree *lc, *rc;
	int mx, l, r;
	tree(){}
	tree(int i, int j){
		l = i, r = j;
		if(l != r){
			int m = (l + r) / 2;
			lc = new tree(l, m);
			rc = new tree(m + 1, r);
		}
	}
	void upd(int i, int x){
		if(l == r) mx = x;
		else{
			if(i <= lc->r) lc->upd(i, x);
			else rc->upd(i, x);
			mx = max(lc->mx, rc->mx);
		}
	};
	int qry(int i, int j){
		if(r < i || j < l) return 0;
		if(i <= l && r <= j) return mx;
		return max(lc->qry(i, j), rc->qry(i, j));
	};
};

struct FT{
	vector<ll> ft;
	int n;
	FT(){}
	FT(int n): n(n), ft(n + 1, 1){}
	void upd(int i, ll x){
		for(; i <= n; i += i & -i){
			ft[i] = ft[i] * x % mod;
		}
	}
	ll qry(int i){
		ll res = 1;
		for(; i > 0; i -= i & -i){
			res = res * ft[i] % mod;
		}
		return res;
	}
};

ll pwr(ll x, ll y){
	ll res = 1;
	while(y){
		if(y % 2){
			res = res * x % mod;
		}
		x = x * x % mod;
		y /= 2;
	}
	return res;
}



tree *st;
FT ft;
set<int> big;

int solve(){
	auto it = big.begin();
	vector<int> hv;
	while(it != big.end() && hv.size() < 30){
		hv.push_back(-(*it));
		it = next(it);
	}
	hv.push_back(-1);
	reverse(hv.begin(), hv.end());
	ll cur = 1;
	if(hv.size() != 1) cur = ft.qry(hv[1]);
	hv.push_back(n);
	vector<pair<int,int>> a;
	for(int i = 0; i < (int) hv.size() - 1; i++){
		if(hv[i] != -1) a.emplace_back(x[hv[i]], y[hv[i]]);
		if(hv[i] + 1 != hv[i + 1]){
			a.emplace_back(1, st->qry(hv[i] + 1, hv[i + 1] - 1));
		}
	}
	for(int i = 0; i < a.size(); i++){
		ll pre = 1;
		ll bst = 0;
		cur = cur * a[i].first % mod;
		for(int j = i + 1; j < a.size(); j++){
			pre *= a[j].first;
			if(pre > 1e9){
				bst = -1;
				break;
			}
			bst = max(bst, pre * a[j].second);
		}
		if(bst != -1 && bst < a[i].second){
			return cur * a[i].second % mod;
		}
	}
	return -1;
}

int init(int N, int X[], int Y[]) {
	n = N;
	x.resize(n), y.resize(n);
	st = new tree(0, n - 1);
	ft = FT(n);
	for(int i = 0; i < n; i++){
		x[i] = X[i];
		y[i] = Y[i];
		st->upd(i, y[i]);
		ft.upd(i + 1, x[i]);
		if(x[i] > 1) big.insert(-i);
	}
	return solve();
}


int updateX(int pos, int val) {	
	if(x[pos] > 1 && val == 1){
		big.erase(-pos);
	}else if(x[pos] == 1 && val > 1){
		big.insert(-pos);
	}
	ft.upd(pos + 1, pwr(x[pos], mod - 2) * val % mod);
	x[pos] = val;
	return solve();
}

int updateY(int pos, int val) {
	st->upd(pos, val);
	y[pos] = val;
	return solve();
}

Compilation message (stderr)

horses.cpp: In member function 'void tree::upd(int, int)':
horses.cpp:22:22: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   22 |  void upd(int i, int x){
      |                  ~~~~^
horses.cpp:7:13: note: shadowed declaration is here
    7 | vector<int> x, y;
      |             ^
horses.cpp: In constructor 'FT::FT(int)':
horses.cpp:41:9: warning: declaration of 'n' shadows a member of 'FT' [-Wshadow]
   41 |  FT(int n): n(n), ft(n + 1, 1){}
      |     ~~~~^
horses.cpp:39:6: note: shadowed declaration is here
   39 |  int n;
      |      ^
horses.cpp:39:6: warning: 'FT::n' will be initialized after [-Wreorder]
horses.cpp:38:13: warning:   'std::vector<long long int> FT::ft' [-Wreorder]
   38 |  vector<ll> ft;
      |             ^~
horses.cpp:41:2: warning:   when initialized here [-Wreorder]
   41 |  FT(int n): n(n), ft(n + 1, 1){}
      |  ^~
horses.cpp: In constructor 'FT::FT(int)':
horses.cpp:41:9: warning: declaration of 'n' shadows a member of 'FT' [-Wshadow]
   41 |  FT(int n): n(n), ft(n + 1, 1){}
      |     ~~~~^
horses.cpp:39:6: note: shadowed declaration is here
   39 |  int n;
      |      ^
horses.cpp: In constructor 'FT::FT(int)':
horses.cpp:41:9: warning: declaration of 'n' shadows a member of 'FT' [-Wshadow]
   41 |  FT(int n): n(n), ft(n + 1, 1){}
      |     ~~~~^
horses.cpp:39:6: note: shadowed declaration is here
   39 |  int n;
      |      ^
horses.cpp: In member function 'void FT::upd(int, ll)':
horses.cpp:42:21: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   42 |  void upd(int i, ll x){
      |                  ~~~^
horses.cpp:7:13: note: shadowed declaration is here
    7 | vector<int> x, y;
      |             ^
horses.cpp: In function 'll pwr(ll, ll)':
horses.cpp:56:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   56 | ll pwr(ll x, ll y){
      |              ~~~^
horses.cpp:7:16: note: shadowed declaration is here
    7 | vector<int> x, y;
      |                ^
horses.cpp:56:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   56 | ll pwr(ll x, ll y){
      |        ~~~^
horses.cpp:7:13: note: shadowed declaration is here
    7 | vector<int> x, y;
      |             ^
horses.cpp: In function 'int solve()':
horses.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i = 0; i < a.size(); i++){
      |                 ~~^~~~~~~~~~
horses.cpp:97:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for(int j = i + 1; j < a.size(); j++){
      |                      ~~^~~~~~~~~~
horses.cpp:99:7: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
   99 |    if(pre > 1e9){
      |       ^~~
horses.cpp:106:29: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  106 |    return cur * a[i].second % mod;
      |           ~~~~~~~~~~~~~~~~~~^~~~~

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