Submission #1098046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098046		azberjibiou	Radio Towers (IOI22_towers)	C++17	23 / 100	4094 ms	4464 KiB

towers

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=500005;
const int mxM=2200005;
const int mxK=61;
const int MOD=1e9+7;
const ll INF=1e18;
struct segtree{
    pii seg[4*mxN];
    pii mrg(pii a, pii b){
        return pii(min(a.fi, b.fi), max(a.se, b.se));
    }
    void init(int idx, int s, int e, vector <int> &v){
        if(s==e){
            seg[idx]=pii(v[s], v[s]);
            return;
        }
        int mid=(s+e)/2;
        init(2*idx, s, mid, v);
        init(2*idx+1, mid+1, e, v);
        seg[idx]=mrg(seg[2*idx], seg[2*idx+1]);
    }
    pii solv(int idx, int s1, int e1, int s2, int e2){
        if(s2>e1 || s1>e2) return pii(MOD, -MOD);
        if(s2<=s1 && e1<=e2) return seg[idx];
        int mid=(s1+e1)/2;
        return mrg(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
    }
};
int N, Q;
int A[mxN];
int qry[mxN][3];
int F[mxN];
/*
void input(){
    cin >> N >> Q;
    A[0]=-1e9-10, A[1]=1e9+10;
    for(int i=2;i<=N+1;i++) cin >> A[i];
    A[N+2]=1e9+10, A[N+3]=-1e9-10;
    for(int i=1;i<=Q;i++){
        int l, r, d;
        cin >> l >> r >> d;
        qry[i][0]=l;
        qry[i][1]=r;
        qry[i][2]=d;
    }
}
*/
segtree T1;
void make_F(){
    vector <int> v(N+4);
    for(int i=0;i<=N+3;i++) v[i]=A[i];
    T1.init(1, 0, N+3, v);
    stack <int> stk;
    stk.push(1);
    for(int i=2;i<=N+1;i++){
        while(A[stk.top()]<A[i]) stk.pop();
        if(A[i]<A[i-1] || A[i]<A[i+1]) continue;
        int mini=(stk.top()==i-1 ? MOD : T1.solv(1, 0, N+3, stk.top()+1, i-1).fi);
        F[i]=A[i]-mini;
        stk.push(i);
    }
    while(stk.size()) stk.pop();

    stk.push(N+2);
    for(int i=N+1;i>=2;i--){
        while(A[stk.top()]<A[i]) stk.pop();
        if(A[i]<A[i-1] || A[i]<A[i+1]) continue;
        int mini=(stk.top()==i+1 ? MOD : T1.solv(1, 0, N+3, i+1, stk.top()-1).fi);
        F[i]=min(F[i], A[i]-mini);
        stk.push(i);
    }
    while(stk.size()) stk.pop();

    stk.push(0);
    for(int i=2;i<=N+1;i++){
        while(A[stk.top()]>A[i]) stk.pop();
        if(A[i]>A[i-1] || A[i]>A[i+1]) continue;
        int maxi=(stk.top()==i-1 ? -MOD : T1.solv(1, 0, N+3, stk.top()+1, i-1).se);
        F[i]=maxi-A[i];
        stk.push(i);
    }

    stk.push(N+3);
    for(int i=N+1;i>=2;i--){
        while(A[stk.top()]>A[i]) stk.pop();
        if(A[i]>A[i-1] || A[i]>A[i+1]) continue;
        int maxi=(stk.top()==i+1 ? -MOD : T1.solv(1, 0, N+3, i+1, stk.top()-1).se);
        F[i]=min(F[i], maxi-A[i]);
        F[i]*=-1;
        stk.push(i);
    }
    //for(int i=1;i<=N;i++) printf("F[%d]=%d\n", i, F[i+1]);
}
void init(int n, vector <int> v){
    N=n;
    A[0]=-1e9-10, A[1]=1e9+10;
    for(int i=2;i<=N+1;i++) A[i]=v[i-2];
    A[N+2]=1e9+10, A[N+3]=-1e9-10;
    make_F();
}
int max_towers(int l, int r, int d){
    l+=2, r+=2;
    int lp=N+3, lm=N+3, rp=0, rm=0, mcnt=0, pcnt=0;
    for(int i=l;i<=r;i++){
        if(F[i]>=d) pcnt++, rp=max(rp, i), lp=min(lp, i);
        if(F[i]<=-d) mcnt++, rm=max(rm, i), lm=min(lm, i);
    }
    if(rp!=0 && rp>=rm){
        bool ok=false;
        for(int i=rp+1;i<=r;i++) if(A[i]<=A[rp]-d) ok=true;
        if(ok) mcnt++;
    }
    if(lp!=N+3 && lp<=lm){
        bool ok=false;
        for(int i=l;i<lp;i++) if(A[i]<=A[lp]-d) ok=true;
        if(ok) mcnt++;
    }
    return (mcnt<=1 ? 1 : mcnt);
}
/*
int main()
{
    gibon
    input();
    make_F();
    for(int i=1;i<=Q;i++){
        printf("%d\n", max_towers(qry[i][0], qry[i][1], qry[i][2]));
    }
} 
*/

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