Submission #225567

#	Time	Username	Problem	Language	Result	Execution time	Memory
225567		nickmet2004	Horses (IOI15_horses)	C++11	100 / 100	780 ms	40576 KiB

horses

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

using namespace std;

const int N = 500005;
const ll mod = 1e9 + 7;

int n;
set<int> changes;
vector<int> x , y;
ll xmult = 1;
int T[1 << 20];

ll Pow(ll a, ll p)
{
    if (p == 0) return 1;
    if (p & 1) return (a * Pow(a, p - 1)) % mod;
    return Pow((a * a) % mod, p / 2);
}
inline ll Inv(ll a) {return Pow(a % mod, mod - 2);}

void upd(int idx , int v , int l = 0 , int r = n - 1 , int pos = 0){
    if(l == r){
        T[pos] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(idx <= mid) upd(idx , v , l , mid , pos * 2 + 1);
    else upd(idx , v , mid + 1 , r , pos * 2 + 2);
    T[pos] = max(T[pos * 2 + 1] , T[pos * 2 + 2]);
}
int get(int L , int R , int l = 0 , int r=  n -1 , int pos = 0){
    if(r < L || R < l) return -2e9;
    if(L <= l && r <= R) return T[pos];
    int mid = (l + r) >> 1;
    return max(get(L , R , l , mid , pos * 2 + 1) , get(L , R , mid + 1 , r , pos *2 +2));
}
struct div{
    ll a , b;
    bool operator<(const div&Q) const {
        return a * Q.b < Q.a * b;
    }
}mx;

int solve(){
    mx.a = 0; mx.b = 1;
    ll curxmult = 1;
    for(auto it = changes.rbegin(); it != changes.rend() && curxmult < 1000000000; ++it){
        int i = *it;
        int j = (it == changes.rbegin() ? n : *prev(it));
        mx = max(mx , {get(i, j - 1) , curxmult});
        curxmult *= x[i];
    }
    ll res = (mx.a * Inv(mx.b)) % mod;
    return res = (res * xmult) % mod;
}
int init(int N , int X[] , int Y[]){
    n = N;
    x.assign(X , X + N);
    y.assign(Y , Y + N);
    for(int i = 0; i < n; ++i){
        upd(i , y[i]);
    }
    changes.insert(0);
    for(int i = 0; i < n; ++i){
        if(x[i] > 1){
            changes.insert(i);
            xmult = (xmult * x[i]) % mod;
        }
    }
    return solve();
}
int updateX(int pos , int val){
    if(pos && x[pos] > 1 && val == 1) changes.erase(pos);
    if(pos && x[pos] == 1 && val > 1) changes.insert(pos);
    xmult = (xmult * Inv(x[pos])) % mod;
    xmult = (xmult * (x[pos] = val))% mod;
    return solve();
}
int updateY(int pos , int val){
    upd(pos , (y[pos] = val));
    return solve();
}
///int main (){}

Compilation message (stderr)

horses.cpp: In function 'int solve()':
horses.cpp:57:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return res = (res * xmult) % mod;
            ~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:59:35: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N , int X[] , int Y[]){
                                   ^
horses.cpp:7:11: note: shadowed declaration is here
 const int N = 500005;
           ^

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