oj.uz

Submission #1053183

# Submission time Handle Problem Language Result Execution time Memory
1053183 2024-08-11T09:29:04 Z hirayuu_oj Radio Towers (IOI22_towers) C++17
0 / 100
 706 ms 11388 KB 
#include "towers.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll INF=1LL<<60;
struct SegTree {
    vector<int> tree;
    int size;
    SegTree(int sz) {
        tree.resize(sz*2,0);
        size=sz;
    }
    void resize(int sz) {
        tree.resize(sz*2,0);
        size=sz;
    }
    void set(int p,int v) {
        p+=size;
        tree[p]=v;
        p/=2;
        while(p>=1) {
            tree[p]=max(tree[p*2],tree[p*2+1]);
            p/=2;
        }
    }
    int prod(int l,int r) {
        int ret=0;
        l+=size;
        r+=size;
        while(l<r) {
            if(l&1) {
                ret=max(ret,tree[l]);
                l++;
            }
            if(r&1) {
                r--;
                ret=max(ret,tree[r]);
            }
            l/=2;
            r/=2;
        }
        return ret;
    }
};
bool flg=false;
vector<int> h;
int n;
SegTree seg(0);
vector<int> lf;
vector<int> hr;
vector<int> ri;
vector<vector<int>> dbl;
bool mountain=true;
int top=-1;
int mx;
void init(int N, std::vector<int> H) {
    bool up=true;
    rng(i,1,N) {
        if(H[i-1]<H[i]) {
            if(!up)mountain=false;
        }
        else {
            top=i-1;
            up=false;
        }
    }
    if(top==-1)top=N-1;
    mx=H[top];
    h=H;
    n=N;
    seg.resize(N);
    rep(i,N) {
        seg.set(i,H[i]);
    }
}
void init_by_d(int d) {
    lf.resize(n+1,n);
    hr.resize(n+1,n);
    ri.resize(n+1,n);
    dbl.resize(20,vector<int>(n+1,0));
    rep(i,n) {
        int ok,ng;
        ok=-1;
        ng=i;
        while(abs(ok-ng)>1) {
            int mid=(ok+ng)/2;
            if(seg.prod(mid,i)>=h[i]+d)ok=mid;
            else ng=mid;
        }
        int l=ok;
        ok=n;
        ng=i;
        while(abs(ok-ng)>1) {
            int mid=(ok+ng)/2;
            if(seg.prod(i,mid+1)>=h[i]+d)ok=mid;
            else ng=mid;
        }
        if(l!=-1) {
            lf[l]=min(lf[l],ok);
            hr[l]=min(hr[l],i);
        }
        ri[i]=ok;
    }
    rrep(i,n) {
        lf[i]=min(lf[i],lf[i+1]);
        ri[i]=min(ri[i],ri[i+1]);
        hr[i]=min(hr[i],hr[i+1]);
    }
    dbl[0]=lf;
    rng(i,1,20) {
        rep(j,n+1) {
            dbl[i][j]=dbl[i-1][dbl[i-1][j]];
        }
    }
}

int max_towers(int L, int R, int D) {
    if(mountain) {
        if(L<=top&&top<=R) {
            if(h[L]+D<=mx&&h[R]+D<=mx)return 2;
        }
        return 1;
    }
    if(!flg) {
        flg=true;
        init_by_d(D);
    }
    if(R<ri[L])return 1;
    int pos=ri[L];
    int ans=1;
    rrep(i,20) {
        if(dbl[i][pos]<=R) {
            ans+=1<<i;
            pos=dbl[i][pos];
        }
    }
    if(hr[pos]<=R)ans++;
    return ans;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 11304 KB Output is correct
2 Correct 706 ms 11216 KB Output is correct
3 Correct 657 ms 11216 KB Output is correct
4 Correct 661 ms 11372 KB Output is correct
5 Correct 663 ms 11216 KB Output is correct
6 Correct 646 ms 11216 KB Output is correct
7 Correct 654 ms 11192 KB Output is correct
8 Correct 514 ms 2392 KB Output is correct
9 Correct 511 ms 2392 KB Output is correct
10 Correct 650 ms 11216 KB Output is correct
11 Correct 660 ms 11388 KB Output is correct
12 Incorrect 536 ms 2392 KB 170th lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 3040 KB 2nd lines differ - on the 1st token, expected: '7063', found: '7197'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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