Submission #956744

#	Time	Username	Problem	Language	Result	Execution time	Memory
956744		Trisanu_Das	Radio Towers (IOI22_towers)	C++17	77 / 100	4016 ms	40476 KiB

towers

#include <bits/stdc++.h>
 
using namespace std;
const int c=100005, sok=2e9+5;
int n, t[c], maxi, fixd;
bool tc1=1, fontos[c];
set<pair<int, int> > tc5;
set<int> pos;
set<pair<int, int> > dif;
int kul(int a, int b) {
    return abs(t[a]-t[b]);
}
 
 
 
vector<vector<pair<int, int>>> rmq_mini, rmq_maxi;
vector<int> rmq_log;
void rmq_init(vector<int> sz) {
    int n=sz.size();
    rmq_log.resize(n+1);
    for (int i=2; i<=n; i++) {
        rmq_log[i]=rmq_log[i/2]+1;
    }
    int po=1, db=1;
    while (po<=n) {
        po*=2, db++;
    }
    rmq_mini.resize(db);
    rmq_maxi.resize(db);
    for (int i=0; i<db; i++) {
        rmq_mini[i].resize(n);
        rmq_maxi[i].resize(n);
    }
    for (int i=0; i<n; i++) {
        rmq_mini[0][i]={sz[i], i};
        rmq_maxi[0][i]={sz[i], i};
    }
    for (int j=1; j<db; j++) {
        for (int i=0; i+(1<<j)<=n; i++) {
            int s=i+(1<<(j-1));
            rmq_mini[j][i]=min(rmq_mini[j-1][i], rmq_mini[j-1][s]);
            rmq_maxi[j][i]=max(rmq_maxi[j-1][i], rmq_maxi[j-1][s]);
        }
    }
}
pair<int, int> rmq_ask(int l, int r, int id) {
    int s=rmq_log[r-l+1], s2=r+1-(1<<s);
    if (!id) {
        return min(rmq_mini[s][l], rmq_mini[s][s2]);
    } else {
        return max(rmq_maxi[s][l], rmq_maxi[s][s2]);
    }
}
 
 
vector<int> spec;
 
 
int try_tc46(int l, int r, int d) {
    if (fixd!=0 && d!=fixd) return 0;
    if (fixd==0) {
        fixd=d;
 
        int ut=sok, utid=0, id=1;
        for (int i=1; i<=n+1; i++) {
            if (id==1) {
                if (t[i]>ut) utid=i;
                ut=max(ut, t[i]);
                if (ut-t[i]>=d) {
                    spec.push_back(utid);
                    utid=i;
                    ut=t[i];
                    id=0;
                }
            } else {
                if (t[i]<ut) utid=i;
                ut=min(ut, t[i]);
                if (t[i]-ut>=d) {
                    spec.push_back(utid);
                    utid=i;
                    ut=t[i];
                    id=1;
                }
            }
        }
 
        spec.push_back(n+1);
 
        /*cout<< "spec: ";
        for (auto x:spec) cout << x << " ";
        cout << "\n";*/
 
    }
 
    int kezd=-1, veg=-1;
    int si=spec.size(), lo=0, hi=si, mid;
    while (hi-lo>1) {
        mid=(hi+lo)/2;
        if (spec[mid]<l) lo=mid;
        else hi=mid;
    }
    kezd=hi;
    if (spec[kezd]>r) return 1;
    lo=0, hi=si;
    while (hi-lo>1) {
        mid=(hi+lo)/2;
        if (spec[mid]>r) hi=mid;
        else lo=mid;
    }
    veg=lo;
    //cout << "sikerult " << kezd << " " << veg << "\n";
    assert(kezd<=veg);
    int ans=(veg+1)/2-(kezd/2);
    int kpos=spec[kezd], vpos=spec[veg];
    if (l<kpos && kezd%2==0 && rmq_ask(l, kpos-1, 0).first+d<=t[kpos]) ans++;
    if (vpos<r && veg%2==0 && rmq_ask(vpos+1, r, 0).first+d<=t[vpos]) ans++;
 
    return ans;
}
void sub(int p) {
    auto it=pos.find(p);
    int el=0, kov=0;
    it++;
    kov=(*it);
    it--, it--;
    el=(*it);
    //cout << "valt " << el << " " << p << " " << kov << "\n";
    pos.erase(p);
    dif.erase({kul(p, kov), p});
    dif.erase({kul(el, p), el});
    dif.insert({kul(el, kov), el});
}
void calc_tc5() {
    fontos[0]=1, fontos[n+1]=1;
    int ut=sok, ans=0, id=1;
    for (int i=1; i<=n+1; i++) {
        if (id==1) {
            ut=max(ut, t[i]);
            if (ut>t[i]) {
                fontos[i-1]=1;
                ut=t[i];
                id=0;
                ans++;
            }
        } else {
            ut=min(ut, t[i]);
            if (t[i]>ut) {
                fontos[i-1]=1;
                ut=t[i];
                id=1;
            }
        }
    }
    int el=-1;
    for (int i=0; i<=n+1; i++) {
        if (!fontos[i]) continue;
        pos.insert(i);
        if (el!=-1) {
            dif.insert({kul(el, i), el});
            //cout << "fontos " << el << " " << i << "\n";
        }
        el=i;
    }
    tc5.insert({0, ans});
    while (ans>1) {
        auto it=dif.begin();
        int ert=(*it).first, p=(*it).second;
        auto it2=pos.upper_bound(p);
        int kov=*it2;
        //cout << "fontos " << p << " " << kov << "\n";
        sub(p), sub(kov);
        ans--;
        //cout << ert << " " << ans << "\n";
        it=tc5.upper_bound({ert, ans});
        if (it!=tc5.end()) tc5.erase(it);
        tc5.insert({ert, ans});
    }
}
void init(int N, vector<int> sz) {
    vector<int> sz2;
    sz2.push_back(sok);
    for (auto x:sz) sz2.push_back(x);
    sz2.push_back(sok);
    rmq_init(sz2);
    n=N;
    for (int i=0; i<n; i++) {
        t[i+1]=sz[i];
        if (t[i+1]>t[maxi]) maxi=i+1;
    }
    t[0]=sok, t[n+1]=sok;
    for (int i=1; i<=n; i++) {
        if (i<maxi && t[i]>t[i+1] || i>maxi && t[i]>t[i-1]) {
            tc1=0;
        }
    }
    calc_tc5();
}
 
int slow(int l, int r, int d) {
    int ut=t[l]+d, ans=0, id=1;
    for (int i=l; i<=r; i++) {
        if (id==1) {
            ut=max(ut, t[i]);
            if (ut-t[i]>=d) {
                ut=t[i];
                id=0;
                ans++;
            }
        } else {
            ut=min(ut, t[i]);
            if (t[i]-ut>=d) {
                ut=t[i];
                id=1;
            }
        }
    }
    return ans;
}
 
int max_towers(int l, int r, int d) {
    l++, r++;
    if (tc1) {
        if (l<=maxi && maxi<=r && max(t[l], t[r])+d<=t[maxi]) return 2;
        return 1;
    }
    if (l==1 && r==n) {
        auto it=tc5.upper_bound({d, 0});
        it--;
        return (*it).second;
    }
    int x=try_tc46(l, r, d);
    if (x) {
        return x;
    }
    return slow(l, r, d);
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:192:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  192 |         if (i<maxi && t[i]>t[i+1] || i>maxi && t[i]>t[i-1]) {
      |             ~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 0 / 23