Submission #153799

#	Time	Username	Problem	Language	Result	Execution time	Memory
153799		alexandra_udristoiu	Horses (IOI15_horses)	C++14	17 / 100	457 ms	524292 KiB

horses

#include<iostream>
#include "horses.h"
#define DIM 500005
#define mod 1000000007
using namespace std;
static int n;
static int x[DIM], y[DIM], lst[DIM];
struct str{
    int prod, xm, ym;
};
static str aint[4 * DIM], aux;
static void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod] = {x[st], x[st], y[st]};
    }
    else{
        int mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
        aint[nod].prod = aint[2 * nod].prod * 1LL * aint[2 * nod + 1].prod % mod;
        aint[nod].xm = max(aint[2 * nod].xm, aint[2 * nod + 1].xm);
        aint[nod].ym = max(aint[2 * nod].ym, aint[2 * nod + 1].ym);
    }
}
static void update(int nod, int st, int dr, int p){
    if(st == dr){
        aint[nod] = {x[st], x[st], y[st]};
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            update(2 * nod, st, mid, p);
        }
        else{
            update(2 * nod + 1, mid + 1, dr, p);
        }
        aint[nod].prod = aint[2 * nod].prod * 1LL * aint[2 * nod + 1].prod % mod;
        aint[nod].xm = max(aint[2 * nod].xm, aint[2 * nod + 1].xm);
        aint[nod].ym = max(aint[2 * nod].ym, aint[2 * nod + 1].ym);
    }
}
static void query(int nod, int st, int dr, int p, int u){
    if(p <= st && dr <= u){
        aux.prod = aux.prod * 1LL * aint[nod].prod % mod;
        aux.xm = max(aux.xm, aint[nod].xm);
        aux.ym = max(aux.ym, aint[nod].ym);
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            query(2 * nod, st, mid, p, u);
        }
        if(u > mid){
            query(2 * nod + 1, mid + 1, dr, p, u);
        }
    }
}
static int solve(){
    int i, p, u, mid, ind, ymax;
    long long val, sol;
    val = 1;
    for(i = n; i >= 1; i--){
        val *= x[i];
        if(val > 1000000000){
            break;
        }
        if(x[i] == 1){
            p = 1;
            u = i;
            while(p <= u){
                mid = (p + u) / 2;
                aux = {1, 0, 0};
                query(1, 1, n, mid, i);
                if(aux.xm == 1){
                    u = mid - 1;
                }
                else{
                    p = mid + 1;
                }
            }
            lst[p] = i;
            i = p;
        }
    }
    val = 1;
    sol = y[i];
    ind = 0;
    for(i = i + 1; i <= n; i++){
        val *= x[i];
        if(x[i] != 1){
            if(val * y[i] > sol){
                sol = val * y[i];
                ind = i;
                ymax = y[i];
            }
        }
        else{
            aux = {1, 0, 0};
            query(1, 1, n, i, lst[i]);
            if(val * aux.ym > sol){
                sol = val * aux.ym;
                ind = lst[i];
                ymax = aux.ym;
            }
            i = lst[i];
        }
    }
    aux = {1, 0, 0};
    query(1, 1, n, 1, ind);
    return aux.prod * 1LL * ymax % mod;
}
int init(int N, int X[], int Y[]) {
	n = N;
	for(int i = 1; i <= n; i++){
        x[i] = X[i - 1];
        y[i] = Y[i - 1];
	}
	build(1, 1, n);
	return solve();
}
int updateX(int pos, int val) {
    pos++;
    x[pos] = val;
    update(1, 1, n, pos);
	return solve();
}
int updateY(int pos, int val) {
    pos++;
    y[pos] = val;
    update(1, 1, n, pos);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:20:76: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[nod].prod = aint[2 * nod].prod * 1LL * aint[2 * nod + 1].prod % mod;
                                                                            ^
horses.cpp: In function 'void update(int, int, int, int)':
horses.cpp:37:76: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[nod].prod = aint[2 * nod].prod * 1LL * aint[2 * nod + 1].prod % mod;
                                                                            ^
horses.cpp: In function 'void query(int, int, int, int, int)':
horses.cpp:44:52: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aux.prod = aux.prod * 1LL * aint[nod].prod % mod;
                                                    ^
horses.cpp: In function 'int solve()':
horses.cpp:110:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return aux.prod * 1LL * ymax % mod;
                                  ^
horses.cpp:110:27: warning: 'ymax' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return aux.prod * 1LL * ymax % mod;
            ~~~~~~~~~~~~~~~^~~~~~

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