Submission #1310031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310031		muhammad-ahmad	Horses (IOI15_horses)	C++20	0 / 100	11 ms	12084 KiB

horses

#include <bits/stdc++.h>
using namespace std;

#include "horses.h"

// #define ll long long
// #define long long long long

const long long N = 5e5 + 5, M = 1e9 + 7;
long long n, cur, x[N], y[N];

struct node {
    long long mxy, px;
    long long left = -1, right = -1;
};

vector<node> T;
set<long long> st;

node join(node a, node b){
    node ans;
    ans.px = (a.px * b.px) % M;
    ans.mxy = max(a.mxy, b.mxy);
    return ans;
}

void build (long long v = 1, long long s = 0, long long e = n){
    if (e - s == 1){
        T[v].mxy = y[s];
        T[v].px = x[s];
        if (x[s] != 1) st.insert(s);
        return;
    }
    
    
    T[v].left = ++cur;
    T.push_back(node());
    T[v].right = ++cur;
    T.push_back(node());
    
    long long lc = T[v].left, rc = T[v].right, mid = (s + e) / 2;
    
    build(lc, s, mid);
    build(rc, mid, e);
    
    T[v] = join(T[lc], T[rc]);
}

node query(long long l, long long r, long long v = 1, long long s = 0, long long e = n){
    if (l <= s && e <= r){
        return T[v];
    }
    if (r <= s or e <= l){
        node temp = node();
        return temp;
    }
    
    long long mid = (s + e) / 2, lc = T[v].left, rc = T[rc].right;
    
    if (r > mid){
        node ans = query(l, r, rc, mid, e);
        if (l < mid){
            ans = join(ans, query(l, r, lc, s, mid));
        }
        return ans;
    }
    return query(l, r, lc, s, mid);
}

void updx(long long pos, long long val, long long v = 1, long long s = 0, long long e = n){
    if (pos < s or e <= pos){
        return;
    }
    if (e - s == 1){
        T[v].px = val;
        return;
    }
    
    long long mid = (s + e) / 2, lc = T[v].left, rc = T[v].right;
    updx(pos, val, lc, s, mid);
    updx(pos, val, rc, mid, e);
    
    T[v] = join(T[lc], T[rc]);
}

void updy(long long pos, long long val, long long v = 1, long long s = 0, long long e = n){
    if (pos < s or e <= pos){
        return;
    }
    if (e - s == 1){
        T[v].mxy = val;
        return;
    }
    
    long long mid = (s + e) / 2, lc = T[v].left, rc = T[v].right;
    updy(pos, val, lc, s, mid);
    updy(pos, val, rc, mid, e);
    
    T[v] = join(T[lc], T[rc]);
}

int init(int N, int X[], int Y[]){
    n = N;
    for (long long i = 0; i < n; i++){
        x[i] = X[i];
        y[i] = Y[i];
    }
    T.push_back(node());
    build();
    
    if (st.empty()){
        return query(0, n).mxy;
    }
    
    auto it = --st.end();
    long long pd = *it;
    while (pd <= 1e9 && it != st.begin()){
        it--;
        pd *= x[*it];
    }
    
    long long ans = 1;
    
    if (pd > 1e9){
        pd /= x[*it];
        ans = query(*it, n).mxy;
        it++;
    }
    
    if (it == st.begin()){
        ans = query(0, *it).mxy;
    }
    
    long long cf = query(0, *it).px, prod = 1;
    
    while (it != st.end()){
        prod *= x[*it];
        ans = max(ans, prod * query(*it, n).mxy);
        it++;
    }
    
    return (((ans % M) * cf) % M);
}

int updateX(int pos, int val){
    if (x[pos] != 1) st.erase(pos);
    x[pos] = val;
    updx(pos, val);
    if (x[pos] != 1) st.insert(pos);
    
    if (st.empty()){
        return query(0, n).mxy;
    }
    
    auto it = --st.end();
    long long pd = *it;
    while (pd <= 1e9 && it != st.begin()){
        it--;
        pd *= x[*it];
    }
    
    long long ans = 1;
    
    if (pd > 1e9){
        pd /= x[*it];
        ans = query(*it, n).mxy;
        it++;
    }
    
    if (it == st.begin()){
        ans = query(0, *it).mxy;
    }
    
    long long cf = query(0, *it).px, prod = 1;
    
    while (it != st.end()){
        prod *= x[*it];
        ans = max(ans, prod * query(*it, n).mxy);
        it++;
    }
    
    return (((ans % M) * cf) % M);
}

int updateY(int pos, int val){
    updy(pos, val);
    
    if (st.empty()){
        return query(0, n).mxy;
    }
    
    auto it = --st.end();
    long long pd = *it;
    while (pd <= 1e9 && it != st.begin()){
        it--;
        pd *= x[*it];
    }
    
    long long ans = 1;
    
    if (pd > 1e9){
        pd /= x[*it];
        ans = query(*it, n).mxy;
        it++;
    }
    
    if (it == st.begin()){
        ans = query(0, *it).mxy;
    }
    
    long long cf = query(0, *it).px, prod = 1;
    
    while (it != st.end()){
        prod *= x[*it];
        ans = max(ans, prod * query(*it, n).mxy);
        it++;
    }
    
    return (((ans % M) * cf) % M);
}

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