Submission #285890

#	Time	Username	Problem	Language	Result	Execution time	Memory
285890		Atill83	말 (IOI15_horses)	C++14	77 / 100	1567 ms	73080 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int MAXN = (int) 5e5 + 5;
const int mod = (int) 1e9+7;
typedef long long ll;
typedef pair<ll, ll> pll;
ll x[MAXN], y[MAXN], pre[MAXN], n;
set<pll> st;
ll bp(ll a, ll b){
	ll res = 1;
	while(b){
		if(b % 2) res = (res * a) % mod;
		a = (a * a) % mod;
		b = b / 2;
	}
	return res;
}


ll t[4*MAXN];
void build(int v, int l, int r){
	if(l == r){ t[v] = y[l];}
	else{
		int m = (l + r) / 2;
		build(2*v, l, m);
		build(2*v + 1, m + 1, r);
		t[v] = max(t[2*v], t[2*v + 1]);
	} 
}

void upd(int v, int tl, int tr, int pos){
	if(tl == tr){
		t[v] = y[tl];
	}else{
		int tm = (tl + tr) / 2;
		if(pos <= tm) 
			upd(2*v, tl, tm, pos);
		else
			upd(2*v + 1, tm + 1, tr, pos);
		t[v] = max(t[2*v], t[2*v + 1]);
	}
}

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

ll ft[MAXN];

void updi(int v, int val){
	for(; v < MAXN; v += (v&-v)){
		ft[v] = (ft[v] * val) % mod;
	}
}

ll get(int v){
	ll res = 1;
	for(; v;  v -= (v&-v)){
		res = (res * ft[v]) % mod;
	}
	return res;
}



ll gt(){
	ll top = 1;
	ll mx = 0;
	auto u = st.end();
	do{
		u--;
		top *= (*u).ss;
	} while(u != st.begin() && top < mod);
	top = 1;
	auto v = u;
	//cerr<<(*u).ff<<" "<<(*u).ss.ff<<endl;
	for(; u != st.end(); u++){
		if(u != v) 
			top *= (*u).ss;
		int l = (*u).ff;
		int r = (next(u) == st.end() ? n : (*next(u)).ff - 1);
		mx = max(mx, top*que(1, 0, n, l, r));
		//cerr<<l<<" "<<r<<" "<<mx<<endl;
	}
	mx %= mod;
	return get((*v).ff) * mx % mod;
}


int init(int N, int X[], int Y[]) {
	n = N;
	for(int i = 0; i <= n; i++) ft[i] = 1;
	for(int i = 1; i <= n; i++){
		x[i] = X[i - 1];
		y[i] = Y[i - 1];
		if(x[i] == 1){
			if(!st.empty() && (*st.rbegin()).ss == 1){

			}else{
				st.insert({i, x[i]});
			}
		}else{
			st.insert({i, x[i]});
		}
		updi(i, x[i]);
	}

	for(int i = 1; i <= n; i++){
		pre[i] = pre[i - 1] * x[i] % mod;
	}

	build(1, 0, n);
	return gt();
}



int updateX(int pos, int val) {	
	pos++;
	updi(pos, bp(x[pos], mod - 2)*val % mod);
	
	if(x[pos] == val){

	}else if(x[pos] == 1){
		x[pos] = val;
		auto u = prev(st.upper_bound({pos, mod}));
		int l = (*u).ff;
		int r;
		if(next(u) == st.end()){
			r = n;
		}else{
			r = (*next(u)).ff - 1;
		}
		st.erase(u);
		if(l != pos)
			st.insert({l, 1});
		if(r != pos)
			st.insert(make_pair(pos + 1, 1));
		st.insert({pos, val});
	}else{
		if(val == 1){
			auto u = st.lower_bound({pos, x[pos]});
			st.erase(u);
			x[pos] = val;
			auto v = st.insert({pos, 1}).ff;
			if(v != st.end()){
				u = v;
				u++;
				if((*u).ss == 1){
					st.erase(u);
				}
			}
			if(v != st.begin()){
				u = v;
				u--;
				if((*u).ss == 1){
					st.erase(v);
				}
			}
		}else{
			auto u = st.lower_bound({pos, x[pos]});
			st.erase(u);
			x[pos] = val;
			st.insert({pos, x[pos]});
		}
	}
	return gt();
}

int updateY(int pos, int val) {
	pos++;
	y[pos] = val;
	upd(1, 0, n, pos);
	return gt();
}

Compilation message (stderr)

horses.cpp: In function 'll gt()':
horses.cpp:3:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    3 | #define ff first
      |            ^
horses.cpp:89:16: note: in expansion of macro 'ff'
   89 |   int l = (*u).ff;
      |                ^~
horses.cpp:90:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   90 |   int r = (next(u) == st.end() ? n : (*next(u)).ff - 1);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:90:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
horses.cpp:91:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   mx = max(mx, top*que(1, 0, n, l, r));
      |                              ^
horses.cpp:3:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    3 | #define ff first
      |            ^
horses.cpp:95:18: note: in expansion of macro 'ff'
   95 |  return get((*v).ff) * mx % mod;
      |                  ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:114:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |   updi(i, x[i]);
      |           ~~~^
horses.cpp:121:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  121 |  build(1, 0, n);
      |              ^
horses.cpp:122:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  122 |  return gt();
      |         ~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:129:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  129 |  updi(pos, bp(x[pos], mod - 2)*val % mod);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:3:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    3 | #define ff first
      |            ^
horses.cpp:136:16: note: in expansion of macro 'ff'
  136 |   int l = (*u).ff;
      |                ^~
horses.cpp:139:8: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  139 |    r = n;
      |        ^
horses.cpp:141:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  141 |    r = (*next(u)).ff - 1;
      |        ~~~~~~~~~~~~~~^~~
horses.cpp:176:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  176 |  return gt();
      |         ~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:182:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  182 |  upd(1, 0, n, pos);
      |            ^
horses.cpp:183:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  183 |  return gt();
      |         ~~^~

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