oj.uz

Submission #1055343

# Submission time Handle Problem Language Result Execution time Memory
1055343 2024-08-12T17:42:48 Z vjudge1 Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 7804 KB 
#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

int n;
vi H, Hord;

map<int, int> NorMap;

void init(int n, vi H0) {
    ::n = n;
    H = H0;
    Hord = H;
    sort(Hord.begin(), Hord.end());
    Hord.resize(unique(Hord.begin(), Hord.end()) - Hord.begin());
    for(int i = 0; i < (int)Hord.size(); ++i) 
        NorMap[Hord[i]] = i;
}

struct AIB { // max pe prefixe
    int n;
    vi V;
    AIB(int N) : n(N + 2), V(N + 2, -1) {}

    void update(int p, int v) {
        ++p;
        while(p < n) {
            V[p] = max(V[p], v);
            p += p & -p;
        }
    }

    int query(int p) {
        ++p;
        if( p < 0 ) return 0;
        int re = 0;
        while(p) {
            re = max(re, V[p]);
            p -= p & -p;
        }
        return re;
    }
};

struct maxSuf {
    int n;
    AIB A;
    maxSuf(int N) : n(N + 1), A(N + 1) {}

    void update(int p, int v) { A.update(n - p - 1, v); }
    int query(int p) { return A.query( n - p - 1); }
};

int max_towers(int l, int r, int D) {
    vi DP0(n, 1), DP1(n, 0);
    ///DP0, ult e statie. DP1 ult e turn

    AIB MP(n);
    maxSuf MS(n);
    int re = 0;

    for (int i = l; i <= r; ++i) {
        int y = H[i];
        if(Hord[0] + D <= y) { /// merita cautat
            int st = 0, dr = int(Hord.size()) - 1, mij;
            while(st < dr) {
                mij = (st + dr + 1) / 2;
                if(Hord[mij] + D <= y) st = mij;
                else dr = mij - 1;
            }
            DP1[i] = max(DP1[i], 1 + MP.query(st));
        }
        MS.update(NorMap[y], DP1[i]);
        if(Hord.back() - D >= y) {
            int st = 0, dr = int(Hord.size()) - 1, mij;
            while(st < dr) {
                mij = (st + dr) / 2;
                if(Hord[st] - D >= y) {
                    dr = mij;
                } else st = mij + 1;
            }
            DP0[i] = max(DP0[i], MS.query(st) + 1);
        }
        MP.update(NorMap[y], DP0[i]);
        re = max(re, (DP0[i] + 1) / 2);
    }
    return re;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4003 ms 5164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '12'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '12'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4045 ms 7804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4049 ms 2448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '12'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4003 ms 5164 KB Time limit exceeded
2 Halted 0 ms 0 KB -