Submission #1359209

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

horses

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

typedef long long ll;
typedef double ld;
typedef pair<ll, ll> pll;

const ll LOG = 34;
const ll MOD = 1000000007;
const ll inf = 1e17;

#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

ll n, p;
vector<ll> x, y;
set<ll> s;
segtree tree;

struct segtree {
    vector<ll> t;
    ll n;
    segtree(vector<ll> x, ll N) {
        n = N;
        t.resize(2 * n);
        for (ll i = 0; i < n; i++) t[i + n] = x[i];
        for (ll i = n - 1; i > 0; i--) {
            t[i] = max(t[i << 1], t[i << 1 | 1]);
        }
    }

    void update(ll i, ll x) {
        i += n;
        t[i] = x;
        for (i >>= 1; i > 0; i >>= 1) {
            t[i] = max(t[i << 1], t[i << 1 | 1]);
        }
    }

    ll query(ll l, ll r) {
        ll lf = -inf, rf = -inf;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) {
                lf = max(lf, t[l++]);
            }
            if (!(r & 1)) {
                rf = max(rf, t[r--]);
            }
        }
        return max(lf, rf);
    }
};

ll binexp(ll b, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = (r * b) % MOD;
        b = (b * b) % MOD;
        e >>= 1;
    }
    return r;
}


int init(int N, int X[], int Y[]) {
    n = N;
    x.resize(n);
    y.resize(n);
    p = 1;
    for (ll i = 0; i < n; i++) {
        x[i] = X[i], y[i] = Y[i];
        if (x[i] > 1) {
            s.insert(i);
        }
    }

    s.insert(0);
    s.insert(n);
    tree = segtree(y, n);
    ll cnt = 0;

    for (auto it = s.begin(); it != s.end() && cnt < n - LOG; cnt++, ++it) {
        p = (p * x[*it]) % MOD;
    }

    return updateX(0, x[0]);
}

bool mod(ll& x) {
    if (x >= MOD) {
        x %= MOD;
        return 1;
    }
    return 0;
}

int updateX(int pos, int val) {
    if (val == 1 && pos != 0) s.erase(pos);
    else s.insert(pos);

    auto it = --s.end();
    ll cnt = 1;
    ll old = -1;

    while (cnt <= LOG) {
        if (cnt == LOG) old = *it;
        --it;
        cnt++;

        if (it == s.begin()) break;
    }

    if (cnt > LOG) {
        if (old > -1) p = p * binexp(x[old], MOD - 2) % MOD;
        p = p * val % MOD;
    }
    x[pos] = val;

    ll res = 1;
    bool up = 0;

    ll cnt = 0;

    for (auto it = --s.end(); ; --it) {
        ll i = *it,
            r = *(++it);
        ll cur_y = tree.query(i, r);
        if (up) {
            res = res * x[i] % MOD;
        } else {
            res = x[i] * max(res, cur_y);
            up |= mod(res);
        }

        ++cnt;
        if (cnt > LOG || it == s.begin()) break;
    }

    return (res * p) % MOD;
}

int updateY(int pos, int val) {
    y[pos] = val;
    tree.update(pos, val);
    
	return updateX(0, x[0]);
}

Compilation message (stderr)

horses.cpp:19:1: error: 'segtree' does not name a type
   19 | segtree tree;
      | ^~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:80:5: error: 'tree' was not declared in this scope; did you mean 'free'?
   80 |     tree = segtree(y, n);
      |     ^~~~
      |     free
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:123:8: error: redeclaration of 'll cnt'
  123 |     ll cnt = 0;
      |        ^~~
horses.cpp:103:8: note: 'll cnt' previously declared here
  103 |     ll cnt = 1;
      |        ^~~
horses.cpp:128:20: error: 'tree' was not declared in this scope; did you mean 'free'?
  128 |         ll cur_y = tree.query(i, r);
      |                    ^~~~
      |                    free
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:145:5: error: 'tree' was not declared in this scope; did you mean 'free'?
  145 |     tree.update(pos, val);
      |     ^~~~
      |     free