Submission #252030

#	Time	Username	Problem	Language	Result	Execution time	Memory
252030		DS007	Horses (IOI15_horses)	C++14	0 / 100	1224 ms	47548 KiB

horses

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

const int N = 5e5, mod = 1e9 + 7;
int n, *x, *y;
set<int> s;

class SegmentTree1 {
    int t[N * 4];

public:
    SegmentTree1() {
        fill(t, t + N * 4, 0);
    }

    void update(int v, int l, int r, int tl, int k) {
        if (l == r && l == tl) {
            t[v] = k;
            return;
        }

        int mid = (l + r) / 2;
        if (tl <= mid)
            update(v * 2, l, mid, tl, k);
        else
            update(v * 2 + 1, mid + 1, r, tl, k);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }

    int query(int v, int l, int r, int tl, int tr) {
        if (tl > tr)
            return -1;
        else if (l == tl && r == tr)
            return t[v];

        int mid = (l + r) / 2;
        return max(query(v * 2, l, mid, tl, min(mid, tr)), query(v * 2 + 1, mid + 1, r, max(tl, mid + 1), tr));
    }
};

class SegmentTree2 {
    int t[N * 4];

public:
    SegmentTree2() {
        fill(t, t + N * 4, 1);
    }

    void update(int v, int l, int r, int tl, int k) {
        if (l == r && l == tl) {
            t[v] = k;
            return;
        }

        int mid = (l + r) / 2;
        if (tl <= mid)
            update(v * 2, l, mid, tl, k);
        else
            update(v * 2 + 1, mid + 1, r, tl, k);
        t[v] = t[v * 2] * t[v * 2 + 1];
    }

    long long query(int v, int l, int r, int tl, int tr) {
        if (tl > tr)
            return 1;
        else if (l == tl && r == tr)
            return t[v];

        int mid = (l + r) / 2;
        return query(v * 2, l, mid, tl, min(mid, tr)) * query(v * 2 + 1, mid + 1, r, max(tl, mid + 1), tr) % mod;
    }
};

SegmentTree1 st1;
SegmentTree2 st2;

int query() {
    auto itr = s.rbegin();
    long long temp = 1;
    vector<int> v;

    while (itr != s.rend() && temp < mod) {
        temp *= x[*itr];
        v.push_back(*itr);
        itr++;
    }

    //for (int i : v)
    //    cerr << i << " ";
    //cerr << endl;

    long long ans = st1.query(1, 0, n - 1, 0, n - 1);

    for (int i = 0; i < v.size(); i++) {
        long long cv = st2.query(1, 0, n - 1, v.back() + 1, v[i]);
        ans = max(ans, cv * st1.query(1, 0, n - 1, v[i], n - 1));
        //cerr << cv << " " << ans << endl;
    }

    ans %= mod;
    return int(st2.query(1, 0, n - 1, 0, v.back()) * ans % mod);
}

int init(int N, int X[], int Y[]) {
	n = N;
	x = X;
	y = Y;

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

	return query();
}

int updateX(int pos, int val) {
    s.erase(pos);
    st2.update(1, 0, n - 1, pos, val);
    x[pos] = val;
    if (val > 1)
        s.insert(pos);
	return query();
}

int updateY(int pos, int val) {
	y[pos] = val;
	st1.update(1, 0, n - 1, pos, val);
	return query();
}

Compilation message (stderr)

horses.cpp: In function 'int query()':
horses.cpp:94:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++) {
                     ~~^~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:104:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:4:11: note: shadowed declaration is here
 const int N = 5e5, mod = 1e9 + 7;
           ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:123:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (val > 1)
     ^~
horses.cpp:125:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  return query();
  ^~~~~~

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