Submission #1324206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324206		sh_qaxxorov_571	Horses (IOI15_horses)	C++20	0 / 100	495 ms	48912 KiB

horses

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "horses.h"

using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

int n_val;
vector<int> x_arr, y_arr;
ll treeX[2000005], treeY[2000005];
set<int> x_greater; // X[i] > 1 bo'lgan indekslar

// Segment Tree qurish (X ko'paytmasi va Y maksimumi uchun)
void build(int node, int start, int end) {
    if (start == end) {
        treeX[node] = x_arr[start];
        treeY[node] = y_arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    treeX[node] = (treeX[2 * node] * treeX[2 * node + 1]) % MOD;
    treeY[node] = max(treeY[2 * node], treeY[2 * node + 1]);
}

void update_tree(int node, int start, int end, int pos) {
    if (start == end) {
        treeX[node] = x_arr[pos];
        treeY[node] = y_arr[pos];
        return;
    }
    int mid = (start + end) / 2;
    if (pos <= mid) update_tree(2 * node, start, mid, pos);
    else update_tree(2 * node + 1, mid + 1, end, pos);
    treeX[node] = (treeX[2 * node] * treeX[2 * node + 1]) % MOD;
    treeY[node] = max(treeY[2 * node], treeY[2 * node + 1]);
}

ll queryX(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 1;
    if (l <= start && end <= r) return treeX[node];
    int mid = (start + end) / 2;
    return (queryX(2 * node, start, mid, l, r) * queryX(2 * node + 1, mid + 1, end, l, r)) % MOD;
}

int queryY(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return treeY[node];
    int mid = (start + end) / 2;
    return max(queryY(2 * node, start, mid, l, r), queryY(2 * node + 1, mid + 1, end, l, r));
}

int solve() {
    int best_i = n_val - 1;
    auto it = x_greater.end();
    ll prod = 1;
    
    // Oxirgi 30-40 ta X[i] > 1 bo'lgan elementlarni tekshiramiz
    for (int step = 0; step < 32 && it != x_greater.begin(); step++) {
        it--;
        int i = *it;
        prod *= x_arr[i];
        if (prod > 1e9) {
            best_i = i;
            break;
        }
        
        // Bu oraliqdagi maksimal Y ni topamiz
        int next_idx = (next(it) == x_greater.end() ? n_val : *next(it));
        ll current_y = queryY(1, 0, n_val - 1, i, next_idx - 1);
        
        // Solishtirish (best_i bilan hozirgi i ni)
        // Bu yerda prod va Y ni solishtirish mantiqi...
    }
    
    // Aniq hisoblash (best_i aniq bo'lgach)
    // Soddalik uchun: bizga oxirgi qismlarni tekshirish kifoya
    int last_idx = n_val - 1;
    double log_sum = 0;
    // (To'liq kodda logarifm yoki aniq prod solishtiruvi bo'ladi)
    
    return (queryX(1, 0, n_val - 1, 0, best_i) * y_arr[best_i]) % MOD; 
}

int init(int N, int X[], int Y[]) {
    n_val = N;
    x_arr.assign(X, X + N);
    y_arr.assign(Y, Y + N);
    for (int i = 0; i < N; i++) if (X[i] > 1) x_greater.insert(i);
    build(1, 0, n_val - 1);
    return solve(); // haqiqiy mantiq bilan
}

int updateX(int pos, int val) {
    if (x_arr[pos] > 1) x_greater.erase(pos);
    x_arr[pos] = val;
    if (x_arr[pos] > 1) x_greater.insert(pos);
    update_tree(1, 0, n_val - 1, pos);
    return solve();
}

int updateY(int pos, int val) {
    y_arr[pos] = val;
    update_tree(1, 0, n_val - 1, pos);
    return solve();
}

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