oj.uz

Submission #1054143

# Submission time Handle Problem Language Result Execution time Memory
1054143 2024-08-12T06:52:26 Z Gray Radio Towers (IOI22_towers) C++17
0 / 100
 499 ms 24016 KB 
#include "towers.h"
#include <algorithm>
#include <vector>
#include <iostream>
#define ll int
#define ff first
#define ss second
#define ln "\n"

using namespace std;
struct SegTree{
     #define node vector<ll>
     vector<node> t;
     ll sz, rsz;
     void init(ll N){
          sz=N*4;
          rsz=N;
          t.resize(sz);
     }
     void clear(){
          t.clear();
          sz=rsz=0;
     }
     void merge(node &p, node &l, node &r){
          ll p1=0, p2=0;
          while (p1<(ll)l.size() or p2<(ll)r.size()){
               if (p2==(ll)r.size() or (p1<(ll)l.size() and l[p1]<r[p1])){
                    p.push_back(l[p1++]);
               }else{
                    p.push_back(r[p2++]);
               }
          }
     }
     void build(ll tl, ll tr, ll v, vector<ll> &a){
          if (tl==tr){
               ll dif=0;
               if (tl-1>=0 and tl+1<(ll)a.size()){
                    dif=max(dif, min(a[tl]-a[tl-1], a[tl]-a[tl+1]));
               }
               t[v].push_back(dif);
          }else{
               ll tm = (tl+tr)/2;
               build(tl, tm, v*2, a);
               build(tm+1, tr, v*2+1, a);
               merge(t[v], t[v*2], t[v*2+1]);
          }
     }
     void build(vector<ll> &a){
          build(0, rsz-1, 1, a);
     }
     void query(ll tl, ll tr, ll v, ll l, ll r, ll D, ll &wr){
          if (tl==l and tr==r){
               wr+=(ll)t[v].size()-(lower_bound(t[v].begin(), t[v].end(), D)-t[v].begin());
          }else if (l>r) return;
          else{
               ll tm = (tl+tr)/2;
               query(tl, tm, v*2, l, min(r, tm), D, wr);
               query(tm+1, tr, v*2+1, max(l, tm+1), r, D, wr);
          }
     }
     ll query(ll l, ll r, ll D){
          ll res=0;
          query(0, rsz-1, 1, l, r, D, res);
          return res;
     }
};

vector<ll> fa;
SegTree tr;
ll fn;
void init(int N, std::vector<int> H) {
     fa=H;
     fn=N;
     tr.clear();
     tr.init(N);
     tr.build(fa);
}
// smallt -> 
// bigt -> 
int max_towers(int L, int R, int D) {
     return tr.query(L+1, R-1, D)+1;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 13912 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 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '5'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '5'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 499 ms 24016 KB 1st lines differ - on the 1st token, expected: '11903', found: '3164'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 184 ms 6024 KB 1st lines differ - on the 1st token, expected: '7197', found: '3706'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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