oj.uz

Submission #638917

# Submission time Handle Problem Language Result Execution time Memory
638917 2022-09-08T01:01:17 Z pigeonbat Radio Towers (IOI22_towers) C++17
0 / 100
 419 ms 5896 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
struct pi{
    int h,x,y;
};
bool operator<(const pi &a, const pi &b){
    return a.h>b.h;
}
priority_queue<pi> pq;
set<int> st;
map<int,int> re;

void init(int N, std::vector<int> H) {
    bool ch = false;
    if(N==1) st.insert(0);
    for(int i=1;i<N;i++){
        if(!ch&&H[i-1]<H[i]){
            st.insert(i-1);
            ch = true;
        }
        else if(ch&&H[i-1]>H[i]){
            st.insert(i-1);
            ch = false;
        }
    }
    if(!ch) st.insert(N-1);
    //for(auto x:st) printf("%d\n",x);
    auto it = st.begin(), nit = it;
    nit++;
    while(nit!=st.end()){
        pq.push({abs(H[*nit]-H[*it]),*it,*nit});
        it++; nit++;
    }
    int d=0;
    while(!pq.empty()){
        int h=pq.top().h,x=pq.top().x,y=pq.top().y; pq.pop();
        if(!st.count(x)||!st.count(y)) continue;
        //printf("%d %d %d %d\n",h,x,y,(int)st.size());
        if(h!=d){
            re[d]=(int)st.size();
            d=h;
        }
        st.erase(x); st.erase(y);
        it=st.lower_bound(x); nit=st.upper_bound(y);
        if(it!=st.begin()&&nit!=st.end()){
            it--;
            pq.push({abs(H[*nit]-H[*it]),*it,*nit});
        }
    }
    re[d]=1;
}

int max_towers(int L, int R, int D) {
    auto it = re.upper_bound(D);
    it--;
    return it->second;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 419 ms 5896 KB 1st lines differ - on the 1st token, expected: '11903', found: '66019'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 320 ms 1556 KB 1st lines differ - on the 1st token, expected: '7197', found: '14393'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

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