oj.uz

Submission #1053182

# Submission time Handle Problem Language Result Execution time Memory
1053182 2024-08-11T09:27:54 Z hirayuu_oj Radio Towers (IOI22_towers) C++17
0 / 100
 713 ms 11400 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=0;
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;
        }
    }
    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 197 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 2 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 2 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 500 ms 11216 KB Output is correct
2 Correct 713 ms 11380 KB Output is correct
3 Correct 601 ms 11228 KB Output is correct
4 Correct 626 ms 11216 KB Output is correct
5 Correct 644 ms 11216 KB Output is correct
6 Correct 639 ms 11380 KB Output is correct
7 Correct 620 ms 11400 KB Output is correct
8 Correct 488 ms 2392 KB Output is correct
9 Correct 495 ms 2392 KB Output is correct
10 Correct 647 ms 11388 KB Output is correct
11 Correct 612 ms 11216 KB Output is correct
12 Incorrect 496 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 204 ms 3044 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 2 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 197 ms 1388 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -