oj.uz

Submission #784832

# Submission time Handle Problem Language Result Execution time Memory
784832 2023-07-16T15:08:17 Z GordonRemzi007 Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 4320 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
 
using namespace std;

class SegmentTree {
    int n;
    vector<int> seggy;
public:
    SegmentTree(int size):n(size) {
        seggy = vector<int>(2*n);
    }
    void update(int x) {
        x+=n;
        seggy[x] = 1;
        while(x > 1) {
            x/=2;
            seggy[x] = seggy[2*x] + seggy[2*x+1];
        }
    }
    int query(int x, int y) {
        int res = 0;
        for(x+=n, y+=n+1; x<y; x/=2, y/=2) {
            if(x&1) res+=seggy[x++];
            if(y&1) res+=seggy[--y];
        }
        return res;
    }
    void print(){
        for(int i = 0; i < 2*n; i++) cout << seggy[i] << "\n";
    }
};
bool srt(pair<int,int> a, pair<int,int> b) {
    return a.first < b.first;
}
vector<int> a;
vector<pair<int,int>>* b = NULL;
SegmentTree* seggy = NULL;

void init(int n, vector<int> h) {
  	a = h;
}
int max_towers(int l, int r, int d) {
    //compute closest left right a[b[i].second]+d array
    vector<int> f(r-l+1), s(r-l+1);
    stack<int> st;
    delete seggy;
    delete b;
    seggy = new SegmentTree(r-l+1);
    b = new vector<pair<int,int>>(r-l+1);
    for(int i = l; i <= r; i++) (*b)[i-l] = {a[i], i-l};
    for(int i = 0; i < b->size(); i++) {
        while(st.size() && (*b)[st.top()].first < (*b)[i].first+d) {
            st.pop();
        }
        if(!st.size()) f[i] = -1;
        else {
            f[i] = st.top();
        }
        st.push((*b)[i].second);
    }
    while(st.size()) st.pop();
    for(int i = b->size()-1; i > -1; i--) {
        while(st.size() && (*b)[st.top()].first < (*b)[i].first+d) {
            st.pop();
        }
        if(!st.size()) s[i] = -1;
        else {
            s[i] = st.top();
        }
        st.push((*b)[i].second);
    }
    sort(b->begin(), b->end(), srt);
    for(int i = 0; i < b->size(); i++) {
        int le = f[(*b)[i].second], ri = s[(*b)[i].second];
        if(le == -1) le = 0;
        if(ri == -1) ri = r-l;
        if(!seggy->query(le, ri)) seggy->update((*b)[i].second);
    }
    return seggy->query(0, r-l);
}

Compilation message

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 0; i < b->size(); i++) {
      |                    ~~^~~~~~~~~~~
towers.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < b->size(); i++) {
      |                    ~~^~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '292', found: '284'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '292', found: '284'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4013 ms 4320 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 4056 ms 1332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '292', found: '284'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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