oj.uz

Submission #897627

# Submission time Handle Problem Language Result Execution time Memory
897627 2024-01-03T14:01:36 Z abcvuitunggio Radio Towers (IOI22_towers) C++17
4 / 100
 666 ms 44884 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=2e9;
int n,h[100001],a[100001],b[100001],id,r[100001],order[100001];
vector <int> ve;
struct PT{
    int sum=0,mn=INF,mx=-INF,l=0,r=0;
}t[2400001];
PT operator +(PT a, PT b){
    return {a.sum+b.sum,min(a.mn,b.mn),max(a.mx,b.mx)};
}
int update(int node, int l, int r, int i){
    id++;
    if (l==r){
        t[id]={1,l,l};
        return id;
    }
    int cur=id;
    t[cur]=t[node];
    int mid=(l+r)>>1;
    if (mid<i)
        t[cur].r=update(t[node].r,mid+1,r,i);
    else
        t[cur].l=update(t[node].l,l,mid,i);
    int x=t[cur].l,y=t[cur].r;
    t[cur]=t[t[cur].l]+t[t[cur].r];
    t[cur].l=x;
    t[cur].r=y;
    return cur;
}
PT get(int node, int l, int r, int u, int v){
    if (l>=u&&r<=v||!node)
        return t[node];
    int mid=(l+r)>>1;
    if (mid+1>v)
        return get(t[node].l,l,mid,u,v);
    if (mid<u)
        return get(t[node].r,mid+1,r,u,v);
    return get(t[node].l,l,mid,u,v)+get(t[node].r,mid+1,r,u,v);
}
struct T{
    int diff,diff2,mx,mn;
}st[400001];
T operator +(T a, T b){
    return {max(max(a.diff,b.diff),h[b.mx]-h[a.mn]),max(max(a.diff2,b.diff2),h[a.mx]-h[b.mn]),(h[a.mx]>h[b.mx]?a.mx:b.mx),(h[a.mn]<h[b.mn]?a.mn:b.mn)};
}
void build(int node, int l, int r){
    if (l==r){
        st[node]={0,0,l,l};
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    st[node]=st[node<<1]+st[node<<1|1];
}
int get(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||u>v||h[st[node].mx]<val)
        return -1;
    if (l==r)
        return l;
    int mid=(l+r)>>1,x=get(node<<1|1,mid+1,r,u,v,val);
    return (x!=-1?x:get(node<<1,l,mid,u,v,val));
}
int get2(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||u>v||h[st[node].mx]<val)
        return n;
    if (l==r)
        return l;
    int mid=(l+r)>>1,x=get2(node<<1,l,mid,u,v,val);
    return (x!=n?x:get2(node<<1|1,mid+1,r,u,v,val));
}
T get3(int node, int l, int r, int u, int v){
    if (l>=u&&r<=v)
        return st[node];
    int mid=(l+r)>>1;
    if (mid+1>v)
        return get3(node<<1,l,mid,u,v);
    if (mid<u)
        return get3(node<<1|1,mid+1,r,u,v);
    return get3(node<<1,l,mid,u,v)+get3(node<<1|1,mid+1,r,u,v);
}
void init(int N, vector <int> H){
    n=N;
    stack <int> st;
    for (int i=0;i<n;i++){
        h[i]=H[i];
        a[i]=b[i]=h[i];
        r[i]=n-1;
        while (!st.empty()&&h[st.top()]>h[i]){
            a[i]=max(a[i],a[st.top()]);
            int x=b[st.top()];
            st.pop();
            if (!st.empty())
                b[st.top()]=max(b[st.top()],x);
        }
        st.push(i);
    }
    build(1,0,n-1);
    for (int i=0;i<n;i++)
        ve.push_back(min(a[i],b[i])-h[i]);
    sort(ve.begin(),ve.end());
    ve.resize(unique(ve.begin(),ve.end())-ve.begin());
    iota(order,order+n,0);
    sort(order,order+n,[](int i, int j){return min(a[i],b[i])-h[i]>min(a[j],b[j])-h[j];});
    for (int j=0;j<n;j++){
        int i=order[j];
        order[j]=lower_bound(ve.begin(),ve.end(),min(a[i],b[i])-h[i])-ve.begin();
        r[order[j]]=update((j?r[order[j-1]]:0),0,n-1,i);
    }
}
int max_towers(int L, int R, int D){
    int res=0,i,j;
    if (D<=ve.back()){
        PT tmp=get(r[lower_bound(ve.begin(),ve.end(),D)-ve.begin()],0,n-1,L,R);
        res=tmp.sum;
        i=tmp.mn;
        j=tmp.mx;
    }
    if (!res){
        i=j=get3(1,0,n-1,L,R).mn;
        res=1;
    }
    int l=get(1,0,n-1,0,i,h[i]+D),r=get2(1,0,n-1,j,n-1,h[j]+D);
    return res+(l>=L&&get3(1,0,n-1,L,l).diff>=D)+(r<=R&&get3(1,0,n-1,r,R).diff2>=D);
}

Compilation message

towers.cpp: In function 'PT get(int, int, int, int, int)':
towers.cpp:33:13: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   33 |     if (l>=u&&r<=v||!node)
      |         ~~~~^~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 26316 KB Output is correct
2 Correct 661 ms 44784 KB Output is correct
3 Correct 662 ms 44608 KB Output is correct
4 Correct 630 ms 44884 KB Output is correct
5 Correct 620 ms 44512 KB Output is correct
6 Correct 664 ms 44840 KB Output is correct
7 Correct 666 ms 44480 KB Output is correct
8 Correct 0 ms 2392 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 2 ms 2904 KB Output is correct
7 Correct 1 ms 2904 KB Output is correct
8 Correct 1 ms 2904 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 1 ms 2904 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2904 KB Output is correct
14 Correct 1 ms 2904 KB Output is correct
15 Correct 1 ms 2904 KB Output is correct
16 Correct 1 ms 2904 KB Output is correct
17 Correct 1 ms 2904 KB Output is correct
18 Correct 1 ms 2912 KB Output is correct
19 Correct 1 ms 2904 KB Output is correct
20 Correct 1 ms 2904 KB Output is correct
21 Correct 2 ms 2904 KB Output is correct
22 Correct 1 ms 2904 KB Output is correct
23 Correct 2 ms 2904 KB Output is correct
24 Incorrect 1 ms 2904 KB 1st lines differ - on the 1st token, expected: '5', found: '4'
25 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 2 ms 2904 KB Output is correct
7 Correct 1 ms 2904 KB Output is correct
8 Correct 1 ms 2904 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 1 ms 2904 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2904 KB Output is correct
14 Correct 1 ms 2904 KB Output is correct
15 Correct 1 ms 2904 KB Output is correct
16 Correct 1 ms 2904 KB Output is correct
17 Correct 1 ms 2904 KB Output is correct
18 Correct 1 ms 2912 KB Output is correct
19 Correct 1 ms 2904 KB Output is correct
20 Correct 1 ms 2904 KB Output is correct
21 Correct 2 ms 2904 KB Output is correct
22 Correct 1 ms 2904 KB Output is correct
23 Correct 2 ms 2904 KB Output is correct
24 Incorrect 1 ms 2904 KB 1st lines differ - on the 1st token, expected: '5', found: '4'
25 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 594 ms 44232 KB 235th lines differ - on the 1st token, expected: '19582', found: '19581'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 12888 KB 87th lines differ - on the 1st token, expected: '1592', found: '1591'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 2 ms 2904 KB Output is correct
7 Correct 1 ms 2904 KB Output is correct
8 Correct 1 ms 2904 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 1 ms 2904 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2904 KB Output is correct
14 Correct 1 ms 2904 KB Output is correct
15 Correct 1 ms 2904 KB Output is correct
16 Correct 1 ms 2904 KB Output is correct
17 Correct 1 ms 2904 KB Output is correct
18 Correct 1 ms 2912 KB Output is correct
19 Correct 1 ms 2904 KB Output is correct
20 Correct 1 ms 2904 KB Output is correct
21 Correct 2 ms 2904 KB Output is correct
22 Correct 1 ms 2904 KB Output is correct
23 Correct 2 ms 2904 KB Output is correct
24 Incorrect 1 ms 2904 KB 1st lines differ - on the 1st token, expected: '5', found: '4'
25 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 26316 KB Output is correct
2 Correct 661 ms 44784 KB Output is correct
3 Correct 662 ms 44608 KB Output is correct
4 Correct 630 ms 44884 KB Output is correct
5 Correct 620 ms 44512 KB Output is correct
6 Correct 664 ms 44840 KB Output is correct
7 Correct 666 ms 44480 KB Output is correct
8 Correct 0 ms 2392 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2904 KB Output is correct
13 Correct 2 ms 2904 KB Output is correct
14 Correct 1 ms 2904 KB Output is correct
15 Correct 1 ms 2904 KB Output is correct
16 Correct 2 ms 2904 KB Output is correct
17 Correct 1 ms 2904 KB Output is correct
18 Correct 1 ms 2904 KB Output is correct
19 Correct 1 ms 2904 KB Output is correct
20 Correct 1 ms 2904 KB Output is correct
21 Correct 1 ms 2904 KB Output is correct
22 Correct 1 ms 2392 KB Output is correct
23 Correct 1 ms 2904 KB Output is correct
24 Correct 1 ms 2904 KB Output is correct
25 Correct 1 ms 2904 KB Output is correct
26 Correct 1 ms 2904 KB Output is correct
27 Correct 1 ms 2904 KB Output is correct
28 Correct 1 ms 2912 KB Output is correct
29 Correct 1 ms 2904 KB Output is correct
30 Correct 1 ms 2904 KB Output is correct
31 Correct 2 ms 2904 KB Output is correct
32 Correct 1 ms 2904 KB Output is correct
33 Correct 2 ms 2904 KB Output is correct
34 Incorrect 1 ms 2904 KB 1st lines differ - on the 1st token, expected: '5', found: '4'
35 Halted 0 ms 0 KB -