Submission #1286527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286527		theiulius	Horses (IOI15_horses)	C++20	Compilation error	0 ms	0 KiB

horses

#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N = 5e2 + 5;
const int MOD = 1e9 + 7;
int tree[4 * N + 1];
int a[N], b[N];
int namr = 1, n = 0;
set<int> s;

int my_pow(int x, int y){
    if (y == 1){
        return x;
    }
    int res = my_pow(x, y / 2) % MOD;
    int b = 1;
    if (y % 2){
        b = y;
    }
    return ((res * res) % MOD * b) % MOD;
}

int my_div(int x){
    return my_pow(x, MOD - 2);
}

// void update(int x, int l, int r, int pos, int val){ // pos da find const ari querize
//     if (l == r){
//         tree[x] = val;
//         return;
//     }
 
//     // orobiti dzebna
//     int mid = (l + r) / 2;
//     if (pos <= mid){ // marcxniv
//         update(2 * x, l, mid, pos, val);
//     }else{
//         update(2 * x + 1, mid + 1, r, pos, val);
//     }
 
//     tree[x] = max(tree[2 * x], tree[2 * x + 1]); // tree[2x] da tree[2x + 1] ukve datvlili gveqneba recursiis gamo
// }
 
// int get(int x, int l, int r, int tl, int tr){ // query const: tl, tr
 
//     if (tl <= l && r <= tr){
//         return tree[x];
//     }
 
//     int mid = (l + r) / 2;
//     int ans = 0;
//     if (tl <= mid){ // marcxniv
//         ans = get(2 * x, l, mid, tl, tr);
//     }
//     if (mid + 1 <= tr){ // marjvniv
//         ans = max(ans, get(2 * x + 1, mid + 1, r, tl, tr));
//     }
 
//     return ans;
// }

void update(int x, int l, int r, int pos, int val){
    b[pos] = val;
}

int get(int x, int l, int r, int tl, int tr){
    int ma = 0;
    for (int i = tl; i <= tr; i++){
        ma = max(ma, b[i]);
    }
    return ma;
}

int my_func(vector<int> x, vector<int> y){
    int ans = 0, ansi = 0, pre = 1;
    for (int i = 0; i < x.size(); i++){
        pre *= x[i];
        if (ans < pre * y[i]){
            ans = pre * y[i];
            ansi = i;
        }
    }
    
    return ansi;
}

int init(int n1, int x[], int y[]) {
    n = n1;
    for (int i = 0; i < n; i++){
        if (x[i] != 1){
            s.insert(i);
        }
    }
    
    for (int i = 0; i < n; i++){
        update(0, 0, n - 1, i, y[i]);
    }

    for (int i = 0; i < n; i++){
        a[i] = x[i];
        b[i] = y[i];
    }
    
    // mtlianis namr
    for (int i = 0; i < n; i++){
        namr *= x[i];
        namr %= MOD;
    }
    
	return 0;
}

int solve(){
    vector<int> x1, y1;
    auto it = s.end();
    it--;
    int suf = 1;
    while (suf < 1e9){
        suf *= (*it);
        
        x1.pb(*it);

        if (it == s.begin()){
            break;
        }
        it--;
    }
    reverse(x1.begin(), x1.end());

    for (int i = 0; i < x1.size() - 1; i++){
        y1.pb(get(0, 0, n - 1, x1[i], x1[i + 1] - 1));
    }
    // (*x.rbegin(), n);
    y1.pb(get(0, 0, n - 1, (*x1.rbegin()), n - 1));
    
    int r = my_func(x1, y1);
    int ans = namr;
    for (int i = r + 1; i < x1.size(); i++){
        ans *= my_div(a[x1[i]]);
    }

    return ans;
}

int updateX(int pos, int val) {
    if (s.count(pos) && val == 1){
        s.erase(pos);
    }else if (!s.count(pos) && val != 1){
        s.insert(pos);
    }
    // namr-is shecvla
    namr = namr * my_div(a[pos]);
    namr *= val;

    a[pos] = val;

	return solve();
}

int updateY(int pos, int val) {
    update(0, 0, n - 1, pos, val);

	return solve();
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccOxVTCU.o: in function `main':
grader.c:(.text.startup+0xa1): undefined reference to `init(int, int*, int*)'
/usr/bin/ld: grader.c:(.text.startup+0xfb): undefined reference to `updateX(int, int)'
/usr/bin/ld: grader.c:(.text.startup+0x155): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status