Submission #579528

#	Time	Username	Problem	Language	Result	Execution time	Memory
579528		JooDdae	Horses (IOI15_horses)	C++17	100 / 100	1491 ms	69844 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define mid ((l+r) >> 1)
 
const ll INF = 1e9+1;
const int mod = 1e9+7;
int n, x[500500], y[500500];
ll t1[2002002], t3[2002002];
array<int, 2> t2[2002002];
set<int> s;
 
ll build1(int node = 1, int l = 0, int r = n-1){
    if(l == r) return t1[node] = x[l];
    return t1[node] = min(INF, build1(node*2, l, mid) * build1(node*2+1, mid+1, r));
}
 
array<int, 2> build2(int node = 1, int l = 0, int r = n-1){
    if(l == r) return t2[node] = {y[l], l};
    return t2[node] = max(build2(node*2, l, mid), build2(node*2+1, mid+1, r));
}
 
ll build3(int node = 1, int l = 0, int r = n-1){
    if(l == r) return t3[node] = x[l];
    return t3[node] = build3(node*2, l, mid) * build3(node*2+1, mid+1, r) % mod;
}
 
void update1(int pos, int val, int node = 1, int l = 0, int r = n-1){
    if(pos < l || r < pos) return;
    if(l == r){
        t1[node] = val;
        return;
    }
    update1(pos, val, node*2, l, mid), update1(pos, val, node*2+1, mid+1, r);
    t1[node] = min(INF, t1[node*2] * t1[node*2+1]);
}
 
void update2(int pos, int val, int node = 1, int l = 0, int r = n-1){
    if(pos < l || r < pos) return;
    if(l == r){
        t2[node][0] = val;
        return;
    }
    update2(pos, val, node*2, l, mid), update2(pos, val, node*2+1, mid+1, r);
    t2[node] = max(t2[node*2], t2[node*2+1]);
}
 
void update3(int pos, int val, int node = 1, int l = 0, int r = n-1){
    if(pos < l || r < pos) return;
    if(l == r){
        t3[node] = val;
        return;
    }
    update3(pos, val, node*2, l, mid), update3(pos, val, node*2+1, mid+1, r);
    t3[node] = t3[node*2] * t3[node*2+1] % mod;
}
 
ll find1(int nl, int nr, int node = 1, int l = 0, int r = n-1){
    if(nr < l || r < nl) return 1;
    if(nl <= l && r <= nr) return t1[node];
    return min(INF, find1(nl, nr, node*2, l, mid) * find1(nl, nr, node*2+1, mid+1, r));
}
 
array<int, 2> find2(int nl, int nr, int node = 1, int l = 0, int r = n-1){
    if(nr < l || r < nl) return {0, 0};
    if(nl <= l && r <= nr) return t2[node];
    return max(find2(nl, nr, node*2, l, mid), find2(nl, nr, node*2+1, mid+1, r));
}
 
ll find3(int nl, int nr, int node = 1, int l = 0, int r = n-1){
    if(nr < l || r < nl) return 1;
    if(nl <= l && r <= nr) return t3[node];
    return find3(nl, nr, node*2, l, mid) * find3(nl, nr, node*2+1, mid+1, r) % mod;
}
 
int find_max(int l, int r){
    if(l == r) return r;
    ll k = 1ll * x[r] * y[r];
    auto mx = find2(l, r-1);
    return k > mx[0] ? r : mx[1];
}
 
int solve(){
    auto it = s.rbegin();
    int mx = find_max(*next(it)+1, *it);
 
    for(int i=0;i<30;i++){
        if(*++it < 0) break;
        int k = find_max(*next(it)+1, *it);
        if(y[k] > find1(k+1, mx) * y[mx]) mx = k;
    }
 
    return find3(0, mx) * y[mx] % mod;
}
 
int init(int N, int X[], int Y[]) {
    n = N;
    for(int i=0;i<N;i++) x[i] = X[i], y[i] = Y[i];
 
    s.insert(-1);
    for(int i=0;i<N;i++) if(x[i] > 1) s.insert(i);
    s.insert(N-1);
 
    build1(), build2(), build3();
 
    return solve();
}
 
int updateX(int pos, int val) { 
    if(pos < n-1 && x[pos] > 1) s.erase(pos);
    x[pos] = val, update1(pos, val), update3(pos, val);
    if(pos < n-1 && x[pos] > 1) s.insert(pos);
    return solve();
}
 
int updateY(int pos, int val) {
    y[pos] = val, update2(pos, val);
    return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int solve()':
horses.cpp:95:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   95 |     return find3(0, mx) * y[mx] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~

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