Submission #117697

#	Time	Username	Problem	Language	Result	Execution time	Memory
117697		zubec	Horses (IOI15_horses)	C++14	77 / 100	1542 ms	34992 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;


const ll MOD = 1e9+7;
const int N = 500100;
const ll MAX = 2000000000;

int n;

int tmx[N*4], a[N], b[N];

pair<int, int> t[N*4], ob[N*4];

void push(int v){
    if (ob[v].first == 0)
        return;
    t[v+v] = t[v+v+1] = ob[v];
    ob[v+v] = ob[v+v+1] = ob[v];
    ob[v] = {0, 0};
}

pair<int, int> get(int v, int l, int r, int pos){
    if (l == r){
        return t[v];
    }
    int mid = (l+r)>>1;
    push(v);
    if (pos <= mid)
        return get(v+v, l, mid, pos); else
        return get(v+v+1, mid+1, r, pos);
}

void update(int v, int l, int r, int tl, int tr, pair<int, int> x){
    if (l > r || tl > r || l > tr || tl > tr)
        return;
    if (tl <= l && r <= tr){
        t[v] = x;
        ob[v] = x;
        return;
    }
    int mid = (l+r)>>1;
    push(v);
    update(v+v, l, mid, tl, tr, x);
    update(v+v+1, mid+1, r, tl, tr, x);
}

void updatemx(int v, int l, int r, int pos, int x){
    if (l == r){
        tmx[v] = x;
        return;
    }
    int mid = (l+r)>>1;
    if (pos <= mid)
        updatemx(v+v, l, mid, pos, x); else
        updatemx(v+v+1, mid+1, r, pos, x);
    tmx[v] = max(tmx[v+v], tmx[v+v+1]);
}

int getmx(int v, int l, int r, int tl, int tr){
    if (l > r || tl > r || l > tr || tl > tr)
        return 0;
    if (tl <= l && r <= tr)
        return tmx[v];
    int mid = (l+r)>>1;
    return max(getmx(v+v, l, mid, tl, tr), getmx(v+v+1, mid+1, r, tl, tr));
}

ld sumLog = 0;

ll mnzh = 1;

ll binpow(ll x, ll y){
    ll res = 1;
    while(y){
        if (y & 1)
            res = (res * x) % MOD;
        y>>=1;
        x = (x * x) % MOD;
    }
    return res;
}

int query(){
    ll cur = 1;
    ll curmnzh = mnzh;
    ld mx = -1;
    ll mxans = 0;
    ld cursum = sumLog;
    for (int i = n; i >= 1; i--){
        if (a[i] == 1){
            pair<int, int> pr = get(1, 1, n, i);
            i = pr.first;
            ll gt = getmx(1, 1, n, pr.first, pr.second);
            if (cursum+log((ld)gt) > mx){
                mx = cursum+log((ld)gt);
                mxans = (curmnzh*gt)%MOD;
            }
        } else {
            ll gt = b[i];
            if (cursum+log((ld)gt) > mx){
                mx = cursum+log((ld)gt);
                mxans = (curmnzh*gt)%MOD;
            }
        }
        //cout << curmnzh << ' ' << cursum << ' ' << cur << ' ' << b[i] << endl;
        curmnzh = (curmnzh * binpow(a[i], MOD-2))%MOD;
        cursum -= log((ld)a[i]);
        cur *= a[i];
        if (cur > MAX)
            break;
    }
    return mxans;
}

int init(int N, int X[], int Y[]) {
    n = N;
    for (int i = 1; i <= n; i++){
        a[i] = X[i-1];
        b[i] = Y[i-1];
        sumLog += log((ld)a[i]);
        mnzh = (mnzh * a[i])%MOD;
        updatemx(1, 1, n, i, b[i]);
        if (a[i] == 1){
            pair<int, int> pr = {i, i};
            if (a[i-1] == 1)
                pr.first = get(1, 1, n, i-1).first;
            update(1, 1, n, pr.first, pr.second, pr);
        }
    }
    return query();
}

int updateX(int pos, int val) {
    ++pos;
    if (a[pos] == 1){
        pair<int, int> pr = get(1, 1, n, pos);
        update(1, 1, n, pr.first, pos-1, {pr.first, pos-1});
        update(1, 1, n, pos+1, pr.second, {pos+1, pr.second});
    }
    mnzh = (mnzh*binpow(a[pos], MOD-2))%MOD;
    sumLog -= log((ld)a[pos]);
    a[pos] = val;
    mnzh = (mnzh*a[pos])%MOD;
    sumLog += log((ld)a[pos]);
    if (a[pos] == 1){
        pair<int, int> pr = {pos, pos};
        if (a[pos-1] == 1)
            pr.first = get(1, 1, n, pos-1).first;
        if (a[pos+1] == 1)
            pr.second = get(1, 1, n, pos+1).second;
        update(1, 1, n, pr.first, pr.second, pr);
    }
    return query();
}

int updateY(int pos, int val) {
    ++pos;
    b[pos] = val;
    updatemx(1, 1, n, pos, val);
    return query();
}

/**

3
2 1 3
3 4 1
1
2 1 2



*/

Compilation message (stderr)

horses.cpp: In function 'int query()':
horses.cpp:116:12: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return mxans;
            ^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:119:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:9:11: note: shadowed declaration is here
 const int N = 500100;
           ^

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