oj.uz

Submission #634088

# Submission time Handle Problem Language Result Execution time Memory
634088 2022-08-23T19:18:00 Z lis05st Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 379196 KB 
//#define _GLIBCXX_DEBUG
//#define _GLIBCXX_DEBUG_PEDANTIC
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include"towers.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

void precalc(){

}
#define MULTITESTS false
void solve(){

}


vector<int>val,pos;
int n;
vector<int>arr;

void build(int v,int l,int r){
    if(l==r){
        val[v]=arr[l];
        pos[v]=l;
        return;
    }
    int m=(l+r)/2;
    build(2*v,l,m);
    build(2*v+1,m+1,r);
    pos[v]=pos[2*v+1];
    val[v]=max(val[2*v],val[2*v+1]);
    if(val[2*v]>val[2*v+1])pos[v]=pos[2*v];
}

int get(int v,int l,int r,int l0,int r0){
    if(l==l0&&r==r0){
        return pos[v];
    }
    int m=(l+r)/2;
    if(r0<=m)return get(2*v,l,m,l0,r0);
    else if(l0>m)return get(2*v+1,m+1,r,l0,r0);
    int A=get(2*v,l,m,l0,m);
    int B=get(2*v+1,m+1,r,m+1,r0);
    int a=arr[A];
    int b=arr[B];
    return (a>b)?A:B;
}

void init(int N, std::vector<int> H){
    arr.swap(H);
    val.resize(4*N+5);
    pos.resize(4*N+5);
    n=N;
    build(1,0,n-1);
}
map<vector<int>,int>mp;
int solve(int L,int R,int D,int LIM=2e9+5){
    if(R<L)return 0;
    if(L==R){
        if(arr[L]<=LIM)return 1;
        return 0;
    }
    if(mp.count({L,R,D,LIM}))return mp[{L,R,D,LIM}];
    int p=get(1,0,n-1,L,R);
    int res=max({
        solve(L,p-1,D,LIM),
        solve(p+1,R,D,LIM),
        solve(L,p-1,D,min(LIM,arr[p]-D))+solve(p+1,R,D,min(LIM,arr[p]-D))
    });
    mp[{L,R,D,LIM}]=res;
    return res;
}
int max_towers(int L, int R, int D){
    return solve(L,R,D);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4062 ms 186216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 7 ms 1232 KB Output is correct
3 Correct 6 ms 1104 KB Output is correct
4 Correct 4 ms 884 KB Output is correct
5 Correct 5 ms 848 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 3 ms 720 KB Output is correct
8 Correct 25 ms 3272 KB Output is correct
9 Correct 108 ms 11620 KB Output is correct
10 Correct 14 ms 2000 KB Output is correct
11 Correct 78 ms 8912 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 495 ms 40556 KB Output is correct
14 Correct 268 ms 24896 KB Output is correct
15 Correct 2 ms 464 KB Output is correct
16 Correct 6 ms 1232 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 63 ms 7496 KB Output is correct
19 Correct 192 ms 17592 KB Output is correct
20 Correct 13 ms 2128 KB Output is correct
21 Correct 9 ms 1616 KB Output is correct
22 Correct 9 ms 1616 KB Output is correct
23 Execution timed out 4083 ms 219836 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 7 ms 1232 KB Output is correct
3 Correct 6 ms 1104 KB Output is correct
4 Correct 4 ms 884 KB Output is correct
5 Correct 5 ms 848 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 3 ms 720 KB Output is correct
8 Correct 25 ms 3272 KB Output is correct
9 Correct 108 ms 11620 KB Output is correct
10 Correct 14 ms 2000 KB Output is correct
11 Correct 78 ms 8912 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 495 ms 40556 KB Output is correct
14 Correct 268 ms 24896 KB Output is correct
15 Correct 2 ms 464 KB Output is correct
16 Correct 6 ms 1232 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 63 ms 7496 KB Output is correct
19 Correct 192 ms 17592 KB Output is correct
20 Correct 13 ms 2128 KB Output is correct
21 Correct 9 ms 1616 KB Output is correct
22 Correct 9 ms 1616 KB Output is correct
23 Execution timed out 4083 ms 219836 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 314900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4051 ms 379196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 7 ms 1232 KB Output is correct
3 Correct 6 ms 1104 KB Output is correct
4 Correct 4 ms 884 KB Output is correct
5 Correct 5 ms 848 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 3 ms 720 KB Output is correct
8 Correct 25 ms 3272 KB Output is correct
9 Correct 108 ms 11620 KB Output is correct
10 Correct 14 ms 2000 KB Output is correct
11 Correct 78 ms 8912 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 495 ms 40556 KB Output is correct
14 Correct 268 ms 24896 KB Output is correct
15 Correct 2 ms 464 KB Output is correct
16 Correct 6 ms 1232 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 63 ms 7496 KB Output is correct
19 Correct 192 ms 17592 KB Output is correct
20 Correct 13 ms 2128 KB Output is correct
21 Correct 9 ms 1616 KB Output is correct
22 Correct 9 ms 1616 KB Output is correct
23 Execution timed out 4083 ms 219836 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4062 ms 186216 KB Time limit exceeded
2 Halted 0 ms 0 KB -