oj.uz

Submission #788678

# Submission time Handle Problem Language Result Execution time Memory
788678 2023-07-20T13:22:58 Z mosiashvililuka Radio Towers (IOI22_towers) C++17
0 / 100
 1088 ms 36648 KB 
#include<bits/stdc++.h>
#include "towers.h"
using namespace std;
const long long N=200000000009;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[200009],K,pas,L,R,D,seg[800009],l,r,z,za,PI,bo[200009],VAL[200009];
vector <pair <long long, long long> > ANS;
multiset <long long> s;
multiset <long long>::iterator it,tt;
multiset <pair <long long, long long> > S;
multiset <pair <long long, long long> >::iterator IT,TT;
pair <long long, long long> P[200009];
void read(long long q, long long w, long long rr){
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        z=max(z,seg[rr]);
        return;
    }
    read(q,(q+w)/2,rr*2);
    read((q+w)/2+1,w,rr*2+1);
}
void UPD(long long i){
    long long D;
    multiset <long long>::iterator it,tt;
    multiset <pair <long long, long long> >::iterator IT,TT;
    tt=s.lower_bound(i);
    tt++;


    if(tt==s.end()){
        R=a+1;
    }else{
        R=(*tt);
    }
    it=s.lower_bound(i);
    if(it==s.begin()){
        L=0;
    }else{
        it--;
        L=(*it);
    }
    L++;R--;



    z=0;
    l=i+1;r=R;
    if(l<=r) read(1,za,1);
    if(r==a) z=N;
    e=z;
    z=0;
    l=L;r=i-1;
    if(l<=r) read(1,za,1);
    if(l==1) z=N;
    e=min(e,z);
    S.erase({VAL[i],i});
    S.insert({e-f[i]+1,i});
}
void init(int NN, std::vector<int> HH) {
    a=NN;
    for(i=1; i<=a; i++){
        f[i]=HH[i-1];
    }
    za=1;
    while(za<a) za*=2;
    for(i=1; i<=a; i++){
        seg[za+i-1]=f[i];
    }
    for(i=za-1; i>=1; i--){
        seg[i]=max(seg[i*2],seg[i*2+1]);
    }

    for(i=1; i<=a; i++){
        PI++;P[PI]={f[i],i};
    }
    sort(P+1,P+PI+1);

    D=1;
    for(ii=1; ii<=PI; ii++){
        i=P[ii].second;
        tt=s.lower_bound(i);
        if(tt==s.end()){
            R=a+1;
        }else{
            R=(*tt);
        }
        it=s.lower_bound(i);
        if(it==s.begin()){
            L=0;
        }else{
            it--;
            L=(*it);
        }
        L++;R--;

        e=0;
        z=0;
        l=i+1;r=R;
        if(l<=r) read(1,za,1);
        if(r==a) z=N;
        if(z<f[i]+D){
            e++;
        }
        z=0;
        l=L;r=i-1;
        if(l<=r) read(1,za,1);
        if(l==1) z=N;
        if(z<f[i]+D){
            e++;
        }
        if(e>0) continue;
        s.insert(i);bo[i]=1;
    }

    ANS.push_back({1,s.size()});

    //cout<<s.size()<<"\n";

    for(i=1; i<=a; i++){
        if(bo[i]==0) continue;
        tt=s.lower_bound(i);
        tt++;


        if(tt==s.end()){
            R=a+1;
        }else{
            R=(*tt);
        }
        it=s.lower_bound(i);
        if(it==s.begin()){
            L=0;
        }else{
            it--;
            L=(*it);
        }
        L++;R--;



        z=0;
        l=i+1;r=R;
        if(l<=r) read(1,za,1);
        if(r==a) z=N;
        e=z;
        z=0;
        l=L;r=i-1;
        if(l<=r) read(1,za,1);
        if(l==1) z=N;
        e=min(e,z);
        S.insert({e-f[i]+1,i});
        VAL[i]=e-f[i]+1;
    }

    /*for(i=1; i<=a; i++){
        if(bo[i]==0) continue;
        cout<<i<<" "<<VAL[i]<<"\n";
    }*/

    while(s.size()>1){
        IT=S.begin();
        D=(*IT).first;
        i=(*IT).second;
        S.erase(IT);
        s.erase(i);

        tt=s.lower_bound(i);
        if(tt!=s.end()){
            UPD((*tt));
        }
        it=tt;
        if(it!=s.begin()){
            it--;
            UPD((*it));
        }

        IT=S.begin();
        if((*IT).first>D){
            ANS.push_back({D,s.size()});
        }
    }
}

int max_towers(int LL, int RR, int DD) {
    pas=1;LL++;RR++;
    L=LL;R=RR;D=DD;


    c=lower_bound(ANS.begin(),ANS.end(),make_pair(D+1,0LL))-ANS.begin();
    c--;
    pas=ANS[c].second;
    return pas;
}

Compilation message

towers.cpp: In function 'void UPD(long long int)':
towers.cpp:22:15: warning: unused variable 'D' [-Wunused-variable]
   22 |     long long D;
      |               ^

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

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