simon

#include <iostream>
#include <math.h>
#include <exception>
#include <limits.h>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <string>

using namespace std;

const int MOD = 100;

class sdmax {

private:
    int counte;
    int * elements;
    int countp;
    int * premax;
    int cnt;

public:
    sdmax(int count) {
        if (count < 0) throw exception();
        counte = count;
        countp = (int)sqrt((double)count);
        elements = new int[counte];
        premax = new int[countp];
        for (int i = 0; i < counte; ++ i)
            elements[i] = 0;
        for (int i = 0; i < countp; ++ i)
            premax[i] = 0;
        cnt = round(1.0 * counte / countp);
    }

    int size() const {
        return counte;
    }

    const int& operator[](const int index) const {
        if (index < 0 || index >= counte) throw exception();
        return elements[index];
    }

    void set(int index, int value) {
        if (index < 0 || index >= counte) throw exception();
        elements[index] = value;
        if (elements[index] > premax[min(index / cnt, countp - 1)])
            premax[min(index / cnt, countp - 1)] = elements[index];
    }

    int max() {
        return *max_element(premax, premax + countp);
    }

    ~sdmax() {
        delete[] elements;
        delete[] premax;
    }
};

void print(const sdmax &a) {
    for (int i = 0; i < a.size(); ++ i) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main(void) {
    time_t t = time(NULL);
    printf("time = %lld\n", t);
    srand(t);

    printf("Input size>");
    int n;
    scanf("%d", &n);
    sdmax a = sdmax(n);
    for (int i = 0; i < n; ++ i) {
        a.set(i, rand() % MOD);
    }
    print(a);
    printf("max = %d\n", a.max());
    return 0;
}