Submission #784832

#	Time	Username	Problem	Language	Result	Execution time	Memory
784832		GordonRemzi007	Radio Towers (IOI22_towers)	C++17	0 / 100	4056 ms	4320 KiB

towers

#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 (stderr)

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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23