Submission #31009

#	Time	Username	Problem	Language	Result	Execution time	Memory
31009		kajebiii	Horses (IOI15_horses)	C++14	17 / 100	229 ms	26428 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MOD = 1e9 + 7;

int N, *X, *Y;
ll myMul(ll x, ll y) {
    if(x < MOD && y < MOD) return x*y;
    return LINF;
}
struct MUL{
    int P; vector<ll> val, mod;
    void merge(int i) {
        val[i] = myMul(val[i*2], val[i*2+1]);
        mod[i] = mod[i*2] * mod[i*2+1] % MOD;
    }
    MUL() {}
    MUL(int n, int nr[]) {
        for(P=1; P<n; P<<=1);
        val = mod = vector<ll>(2*P, 1);
        for(int i=0; i<n; i++) val[P+i] = mod[P+i] = nr[i];
        for(int i=P-1; i>=1; i--) merge(i);
    }
    void updateX(int v, int k) {
        X[v] = k;
        v += P;
        val[v] = mod[v] = k;
        while(v/=2) merge(v);
    }
    ll getMul(int a, int b) {
        ll res = 1;
        for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
            if(a%2==1) res = myMul(res, val[a++]);
            if(b%2==0) res = myMul(res, val[b--]);
        }
        return res;
    }
    ll getMod(int a, int b) {
        ll res = 1;
        for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
            if(a%2==1) res = res * mod[a++] % MOD;
            if(b%2==0) res = res * mod[b--] % MOD;
        }
        return res;
    }
}Mul;

struct IDX{
    int P; vector<int> ix;
    void merge(int i) {
        int l = ix[i*2], r = ix[i*2+1];
        int res = -1;
        if(r == -1) res = l;
        else{
            ll mul = Mul.getMul(l+1, r);
            if(mul >= MOD) res = r;
            else{
                if(Y[l] >= mul * Y[r]) res = l;
                else res = r;
            }
        }
        ix[i] = res;
    }
    IDX() {}
    IDX(int n, int nr[]) {
        for(P=1; P<n; P<<=1);
        ix = vector<int>(2*P, -1);
        for(int i=0; i<n; i++) ix[P+i] = i;
        for(int i=P-1; i>=1; i--) merge(i);
    }
    void updateY(int v, int k) {
        Y[v] = k;
        v += P;
        while(v/=2) merge(v);
    }
    int getMax() {return ix[1];}
}Idx;
int getAns() {
    int ans = Idx.getMax();
    return Mul.getMod(0, ans) * Y[ans] % MOD;
}
int init(int n, int x[], int y[]) {
    N = n; X = x; Y = y;
    Mul = MUL(n, x);
    Idx = IDX(n, y);
	return getAns();
}

int updateX(int pos, int val) {	
    Mul.updateX(pos, val);
	return getAns();
}

int updateY(int pos, int val) {
    Idx.updateY(pos, val);
	return getAns();
}

Compilation message (stderr)

horses.cpp:81:23: warning: unused parameter 'nr' [-Wunused-parameter]
     IDX(int n, int nr[]) {
                       ^
horses.cpp: In function 'int getAns()':
horses.cpp:96:42: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return Mul.getMod(0, ans) * Y[ans] % MOD;
                                          ^

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