Submission #702761

#	Time	Username	Problem	Language	Result	Execution time	Memory
702761		lukameladze	Horses (IOI15_horses)	C++14	100 / 100	764 ms	73808 KiB

horses

# include "horses.h"
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair <ll, ll>
 
const ll NN = 5e5 + 5, inf = 2e9, mod = 1e9 + 7; 
long long n, x[NN],y[NN],tree_ml[4 * NN];
pii tree_mx[4 * NN]; 
long long merge_ml(ll a, ll b) {
    return (a * b) % mod;
}
pii merge_mx(pii a, pii b) {
    return max(a, b);
}
void build(ll node, ll le, ll ri) {
    if (le == ri) {
        tree_ml[node] = x[le];
        tree_mx[node] = {y[le], le};
        return ;
    }
    ll mid = (le + ri) / 2;
    build(2 * node, le, mid);
    build(2 * node + 1, mid + 1, ri);
    tree_ml[node] = merge_ml(tree_ml[2 * node], tree_ml[2 * node + 1]);
    tree_mx[node] = merge_mx(tree_mx[2 * node], tree_mx[2 * node + 1]);
}
void update(ll node, ll le, ll ri, ll idx, ll val, ll ty) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        if (ty == 0) tree_ml[node] = x[le];
        else tree_mx[node] = {y[le], le};
        return ;
    }
    ll mid = (le + ri) / 2;
    update(2 * node,le, mid,idx,val,ty);
    update(2 * node + 1, mid + 1, ri, idx,val,ty);
    tree_ml[node] = merge_ml(tree_ml[2 * node], tree_ml[2 * node + 1]);
    tree_mx[node] = merge_mx(tree_mx[2 * node], tree_mx[2 * node + 1]);
}
ll get_ml(ll node, ll le, ll ri, ll start, ll end) {
    if (le > end || ri < start || start > end) return 1LL;
    if (le >= start && ri <= end) return tree_ml[node];
    ll mid = (le + ri) / 2;
    return merge_ml(get_ml(2 * node, le, mid, start,end), get_ml(2 * node + 1, mid + 1, ri, start, end));
}
pii get_mx(ll node, ll le, ll ri, ll start, ll end) {
   if (le > end || ri < start || start > end) return {-1e9, 0LL};
   if (le >= start && ri <= end) return tree_mx[node];
   ll mid = (le + ri) / 2;
   return merge_mx(get_mx(2 * node, le, mid,start,end), get_mx(2 * node + 1, mid + 1, ri, start, end)); 
}
set <ll> s;
ll go() {
    auto it = --s.end(); // n + 1
    auto it1 = it; it--;
    ll cur_mx = 1, cnt = 0, optid = n;
    while (true) {
        cnt++;
        ll st_y = (*it); ll nd_y = (*it1) - 1;
        if (st_y == 0) st_y++;
        ll mx_y = get_mx(1,1,n,st_y, nd_y).f;
        if (mx_y > cur_mx) {
            optid = get_mx(1,1,n, st_y, nd_y).s;
            cur_mx = mx_y;
        }
        cur_mx *= x[st_y];
        if (it1 == s.begin() || cnt > 32 || cur_mx > inf) break;
        it--; it1--;
    }
    return (get_ml(1,1,n,1,optid) * y[optid]) % mod;
}
int init(int N, int X[], int Y[]) {
    n = N;
    x[0] = 1; y[0] = 1;
    for (int i = 1; i <= n; i++) {
        x[i] = X[i - 1]; y[i] = Y[i - 1];
        if (x[i] != 1) s.insert(i);
    }
    s.insert(0); s.insert(n + 1);
    build(1, 1, n);
	return go();
}
 
int updateX(int pos, int val) {	
    pos++;
    if (x[pos] != 1) {
        s.erase(pos);
    }
    x[pos] = val;
    update(1,1,n, pos,val,0);
    if (x[pos] != 1) s.insert(pos);
    return go();
}
 
int updateY(int pos, int val) {
    pos++;
    y[pos] = val;
    update(1,1,n, pos,val, 1);
    return go();
}
/*
main() {
    int N;
    cin>>N;
	int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
	int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
 
	for (int i = 0; i < N; i++) {
		cin>>X[i];
	}
 
	for (int i = 0; i < N; i++) {
		cin>>Y[i];
	}	
 
	cout<<init(N,X,Y)<<"\n";
    int M;
	cin>>M;
 
	for (int i = 0; i < M; i++) {
		int type; cin>>type;
		int pos; cin>>pos;
		int val; cin>>val; 
 
		if (type == 1) {
			cout<<updateX(pos,val)<<"\n";
		} else if (type == 2) {
			cout<<updateY(pos,val)<<"\n";
		}
	}
 
	return 0;
}*/

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:84:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   84 |  return go();
      |         ~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:95:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   95 |     return go();
      |            ~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:102:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |     return go();
      |            ~~^~

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