Submission #521819

#	Time	Username	Problem	Language	Result	Execution time	Memory
521819		Leo121	Horses (IOI15_horses)	C++14	100 / 100	126 ms	29616 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int lim = 5e5;
bool stbool[4 * lim + 2];
int stmax[4 * lim + 2];
ll bit[lim + 2];
int n;
ll x[lim + 2];
int y[lim + 2];
int posicion[33];
ll valor[33];
int mayor[33];
int dif1 = 0;
ll expb(ll numero){
    ll res = 1LL;
    int aux = 1e9 + 5;
    forn(i, 0, 29){
        if(((1 << i) & aux)){
            res *= numero;
            res %= mod;
        }
        numero *= numero;
        numero %= mod;
    }
    return res;
}
void initbool(int nodo, int l, int r){
    if(l == r){
        stbool[nodo] = (x[l] != 1);
        return;
    }
    int mitad = (l + r) / 2;
    initbool(nodo * 2, l, mitad);
    initbool(nodo * 2 + 1, mitad + 1, r);
    stbool[nodo] = stbool[nodo * 2] | stbool[nodo * 2 + 1];
}
int querybool(int nodo, int l, int r, int rango){
    if(l > rango){
        return 0;
    }
    if(!stbool[nodo]){
        return 0;
    }
    if(l == r){
        return l;
    }
    int mitad = (l + r) / 2, value;
    value = querybool(nodo * 2 + 1, mitad + 1, r, rango);
    if(!value){
        value = querybool(nodo * 2, l, mitad, rango);
    }
    return value;
}
void updatebool(int nodo, int l, int r, int pos){
    if(pos < l || pos > r){
        return;
    }
    if(pos == l && pos == r){
        stbool[nodo] ^= 1;
        return;
    }
    int mitad = (l + r) / 2;
    updatebool(nodo * 2, l, mitad, pos);
    updatebool(nodo * 2, mitad + 1, r, pos);
    stbool[nodo] = stbool[nodo * 2] | stbool[nodo * 2 + 1];
}
void initmax(int nodo, int l, int r){
    if(l == r){
        stmax[nodo] = y[l];
        return;
    }
    int mitad = (l + r) / 2;
    initmax(nodo * 2, l, mitad);
    initmax(nodo * 2 + 1, mitad + 1, r);
    stmax[nodo] = max(stmax[nodo * 2], stmax[nodo * 2 + 1]);
}
int querymax(int nodo, int l, int r, int li, int ls){
    if(li > r || ls < l){
        return 0;
    }
    if(li <= l && ls >= r){
        return stmax[nodo];
    }
    int mitad = (l + r) / 2;
    return max(querymax(nodo * 2, l, mitad, li, ls), querymax(nodo * 2 + 1, mitad + 1, r, li, ls));
}
void updatemax(int nodo, int l, int r, int pos, int val){
    if(pos < l || pos > r){
        return;
    }
    if(pos == l && pos == r){
        stmax[nodo] = val;
        return;
    }
    int mitad = (l + r) / 2;
    updatemax(nodo * 2, l, mitad, pos, val);
    updatemax(nodo * 2 + 1, mitad + 1, r, pos, val);
    stmax[nodo] = max(stmax[nodo * 2], stmax[nodo * 2 + 1]);
}
void updatebit(int pos, ll valorxd){
    for(int i = pos; i <= n; i += i & -i){
        bit[i] *= valorxd;
        bit[i] %= mod;
    }
}
ll querybit(int pos){
    ll res = 1LL;
    for(int i = pos; i >= 1; i -= i & -i){
        res *= bit[i];
        res %= mod;
    }
    return res;
}
ll respuesta(){
    int indice = 1;
    ll auxiliar = 1LL, res;
    if(n < 30){
        forn(i, 2, n){
            auxiliar *= x[i];
            if(auxiliar < (ll) y[indice]){
                auxiliar *= (ll) y[i];
            }
            if(auxiliar >= (ll) y[indice]){
                indice = i;
                auxiliar = 1LL;
            }
            else{
                auxiliar /= (ll) y[i];
            }
        }
        res = querybit(indice);
        res *= (ll) y[indice];
        res %= mod;
    }
    else{
        forn(i, 2, 30){
            auxiliar *= valor[i];
            if(auxiliar < (ll) mayor[indice] && mayor[i]){
                auxiliar *= (ll) mayor[i];
            }
            if(auxiliar >= (ll) mayor[indice]){
                auxiliar = 1LL;
                indice = i;
            }
            else if(mayor[i]){
                auxiliar /= (ll) mayor[i];
            }
        }
        res = (valor[indice] == 1LL) ? 1LL :  querybit(posicion[indice]);
        res *= (ll) mayor[indice];
        res %= mod;

    }
    return res;
}
int init(int N, int X[], int Y[]) {
    n = N;
    forn(i, 0, n - 1){
        x[i + 1] = (ll) X[i];
        y[i + 1] = Y[i];
        bit[i + 1] = 1;
    }
    initbool(1, 1, n);
    initmax(1, 1, n);
    forn(i, 1, n){
        if(x[i] != 1){
            updatebit(i, x[i]);
            dif1 ++;
        }
    }
    posicion[31] = n + 1;
    ll res;
    if(n >= 30){
        fora(i, 30, max(1, 31 - dif1)){
            posicion[i] = querybool(1, 1, n, posicion[i + 1] - 1);
            valor[i] = x[posicion[i]];
            mayor[i] = querymax(1, 1, n, posicion[i], posicion[i + 1] - 1);
        }
        fora(i, max(1, 31 - dif1) - 1, 1){
            posicion[i] = 0;
            valor[i] = 1LL;
            if(posicion[i + 1]){
                mayor[i] = querymax(1, 1, n, 1, posicion[i + 1] - 1);
            }
            else{
                mayor[i] = mayor[i + 1];
            }
        }
    }
    /**forn(i, 1, 30){
        cout << posicion[i] << " " << mayor[i] << " " << valor[i] << "\n";
    }*/
    res = respuesta();
	return (int) res;
}

int updateX(int pos, int val) {
	ll actualiza =  x[pos + 1];
	if(val != (ll) actualiza){
        actualiza = expb(actualiza);
        actualiza *= (ll) val;
        actualiza %= mod;
        updatebit(pos + 1, actualiza);
        if(val == 1){
            updatebool(1, 1, n, pos + 1);
            dif1 --;
        }
        if(val > 1 && x[pos + 1] == 1){
            updatebool(1, 1, n, pos + 1);
            dif1 ++;
        }
        if(n >= 30){
            if(val == 1){
                if(pos + 1 > posicion[1]){
                    forn(i, 2, 30){
                        if(posicion[i] == pos + 1){
                            posicion[i] = posicion[i - 1];
                            mayor[i] = max(mayor[i], mayor[i - 1]);
                            valor[i] = valor[i - 1];
                            fora(j, i - 1, 2){
                                posicion[j] = posicion[j - 1];
                                mayor[j] = mayor[j - 1];
                                valor[j] = valor[j - 1];
                            }
                            break;
                        }
                    }
                }
                if(pos + 1 >= posicion[1]){
                    if(dif1 >= 30){
                        posicion[1] = querybool(1, 1, n, posicion[2] - 1);
                        mayor[1] = querymax(1, 1, n, posicion[1], posicion[2] - 1);
                        valor[1] = x[posicion[1]];
                    }
                    else{
                        posicion[1] = 0;
                        mayor[1] = querymax(1, 1, n, 1, posicion[31 - dif1] - 1);
                        valor[1] = 1LL;
                    }
                }
            }
            else if(x[pos + 1] > 1 && posicion[1] <= pos + 1){
                forn(i, 1, 30){
                    if(posicion[i] == pos + 1){
                        valor[i] = (ll) val;
                        break;
                    }
                }
            }
            else if(x[pos + 1] == 1 && posicion[1] < pos + 1){
                forn(i, 1, 30){
                    if(posicion[i + 1] > pos + 1){
                        posicion[i] = pos + 1;
                        valor[i] = (ll) val;
                        mayor[i] =  querymax(1, 1, n, pos + 1, posicion[i + 1] - 1);
                        if(i != 1){
                            if(posicion[i - 1] == 0){
                                mayor[i - 1] = querymax(1, 1, n, 1, pos);
                                fora(j, i - 2, 1){
                                    mayor[j] = mayor[j + 1];
                                }
                            }
                            else{
                                mayor[i - 1] = querymax(1, 1, n, posicion[i - 1], pos);
                            }
                        }
                        break;
                    }
                    else{
                        posicion[i] = posicion[i + 1];
                        mayor[i] = mayor[i + 1];
                        valor[i] = valor[i + 1];
                    }
                }
            }
        }
        x[pos + 1] = (ll) val;
        /**forn(i, 1, 30){
            cout << posicion[i] << " " << mayor[i] << " " << valor[i] << "\n";
        }*/
	}
	ll res = respuesta();
	return (int) res;
}

int updateY(int pos, int val) {
	updatemax(1, 1, n, pos + 1, val);
	y[pos + 1] = val;
	if(n >= 30){
        fora(i, 30, 1){
            if(pos + 1 >= posicion[i]){
                mayor[i] = querymax(1, 1, n, (posicion[i] == 0) ? 1 : posicion[i], posicion[i + 1] - 1);
                if(posicion[i] == 0){
                    fora(j, i - 1, 1){
                        mayor[j] = mayor[j + 1];
                    }
                }
                break;
            }
        }
        /**forn(i, 1, 30){
            cout << posicion[i] << " " << mayor[i] << " " << valor[i] << "\n";
        }*/
	}
	ll res = respuesta();
	return (int) res;
}

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