oj.uz

Submission #782286

# Submission time Handle Problem Language Result Execution time Memory
782286 2023-07-13T18:34:40 Z FEDIKUS Radio Towers (IOI22_towers) C++17
14 / 100
 959 ms 85564 KB 
#include "towers.h"

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int,int>;
using mim = pair<pii,pii>;

const int maxn=1e5+10;
const int logg=18;

int n;
int h[maxn];
multiset<pii > res;
mim sparse[logg][maxn];
int klk;
int uniq[maxn];
pair<int,int> najs[2][logg][maxn];

mim comb(mim &a,mim &b){
  mim ret=a;
  ret.first=max(ret.first,b.first);
  ret.second=min(ret.second,b.second);
  return ret;
}

mim qry(int l,int r){
  mim ret={{h[l],l},{h[l],l}};
  for(int i=logg-1;i>=0;i--){
    if(r-(1<<i)+1>=l){
      ret=comb(ret,sparse[i][r]);
      r-=(1<<i);
    }
  }
  return ret;
}

void resi(int l,int r,multiset<pii > &ret,int naj=2e9+10){
  if(r<l) return;
  najs[0][0][l]=max(najs[0][0][l],{naj,l});
  najs[1][0][r]=max(najs[1][0][r],{naj,r});
  auto temp=qry(l,r);
  pii maxi=temp.first;
  pii mini=temp.second;
  multiset<pii> levi; multiset<pii> desni;
  resi(l,maxi.second-1,levi,maxi.first);
  resi(maxi.second+1,r,desni,maxi.first);
  if(levi.size()>desni.size()) swap(levi,desni);
  for(auto i:desni) levi.emplace(i);
  if(!levi.empty()){
    auto najv=--levi.end();
    int d=naj-mini.first;
    if((*najv).first<d){
        levi.erase(najv);
        levi.emplace(pii(d,mini.second));
    }
  }else{
    levi.emplace(pii(naj-mini.first,mini.second));
  }
  swap(ret,levi);
}

void init(int _n, vector<int> _h) {
  n=_n;
  for(int i=0;i<n;i++) najs[0][0][i]=najs[1][0][i]={-1,-1};
  for(int i=0;i<n;i++) h[i]=_h[i];
  for(int i=0;i<logg;i++){
    for(int j=0;j<n;j++){
      if(i==0) sparse[i][j]={{h[j],j},{h[j],j}};
      else if(j-(1<<(i-1))>=0) sparse[i][j]=comb(sparse[i-1][j],sparse[i-1][j-(1<<(i-1))]);
      else sparse[i][j]=sparse[i-1][j];
  	}
  }
  resi(0,n-1,res);
  for(int i=1;i<logg;i++){
    for(int j=0;j<n;j++){
      if(j-(1<<(i-1))>=0) najs[0][i][j]=max(najs[0][i-1][j],najs[0][i-1][j-(1<<(i-1))]);
      else najs[0][i][j]=najs[0][i-1][j];

      if(j-(1<<(i-1))>=0) najs[1][i][j]=max(najs[1][i-1][j],najs[1][i-1][j-(1<<(i-1))]);
      else najs[1][i][j]=najs[1][i-1][j];
    }
  }
}

pii najupit(int l,int r,int koji){
  pii ret={-1,-1};
  for(int i=logg-1;i>=0;i--){
    if(r-(1<<i)+1>=l){
      ret=max(ret,najs[koji][i][r]);
      r-=(1<<i);
    }
  }
  return ret;
}

int D=-1;

pair<int,pii> segt[4*maxn+10];

pair<int,pii> combseg(const pair<int,pii> a,const pair<int,pii> b){
	pair<int,pii> ret;
	ret.first=a.first+b.first;
	ret.second.first=max(a.second.first,b.second.first);
	ret.second.second=min(a.second.second,b.second.second);
	return ret;
}

void update(int t,int v,int ind=1,int l=0,int r=n-1){
  if(l==r){
		segt[ind]={1,{v,v}};
		return;
	}
	int mid=l+(r-l)/2;
	if(t<=mid) update(t,v,2*ind,l,mid);
	else update(t,v,2*ind+1,mid+1,r);
	segt[ind]=combseg(segt[2*ind],segt[2*ind+1]);
}

pair<int,pii> query(int tl,int tr,int ind=1,int l=0,int r=n-1){
	if(tl<=l && r<=tr) return segt[ind];
	int mid=l+(r-l)/2;
	if(tr<=mid) return query(tl,tr,2*ind,l,mid);
	if(tl>mid) return query(tl,tr,2*ind+1,mid+1,r);
	return combseg(query(tl,tr,2*ind,l,mid),query(tl,tr,2*ind+1,mid+1,r));
}

int max_towers(int l, int r, int d) {
  if(D==-1){
			for(int i=0;i<4*maxn+10;i++) segt[i]={0,{-1,INT_MAX}};
      for(auto i:res){
          if(i.first>=d) update(i.second,i.second);
      }
      D=d;
  }
	if(l==r) return 1;
	if(r==l+1) return 1;
	auto temp=query(l,r);
  int ret=temp.first;
	int prvi=temp.second.second;
	int posl=temp.second.first;
	if(prvi==INT_MAX){
		prvi=r+1;
		posl=l-1;
	}

	// za levo
	if(prvi-1>=l){
		auto tmp=najupit(l,prvi-1,1);
		int koji=tmp.second;
		int naj=tmp.first;
		if(qry(l,koji).second.first<=naj-d) ret++;
	}
	// za desno
	if(posl+1<=r){
		auto tmp=najupit(posl+1,r,0);
		int koji=tmp.second;
		int naj=tmp.first;
		if(qry(koji,r).second.first<=naj-d) ret++;
	}
  return ret;
}
/*
7 1
1 10 4 11 15 12 3  
3 5 1
*/

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5456 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 4 ms 6436 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 4 ms 6500 KB Output is correct
7 Correct 4 ms 6480 KB Output is correct
8 Incorrect 3 ms 6864 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5456 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 4 ms 6436 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 4 ms 6500 KB Output is correct
7 Correct 4 ms 6480 KB Output is correct
8 Incorrect 3 ms 6864 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
9 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 64284 KB Output is correct
2 Correct 782 ms 64868 KB Output is correct
3 Correct 903 ms 64552 KB Output is correct
4 Correct 882 ms 66448 KB Output is correct
5 Correct 854 ms 65952 KB Output is correct
6 Correct 928 ms 66748 KB Output is correct
7 Correct 842 ms 65748 KB Output is correct
8 Correct 868 ms 85560 KB Output is correct
9 Correct 891 ms 85548 KB Output is correct
10 Correct 959 ms 79556 KB Output is correct
11 Correct 886 ms 79620 KB Output is correct
12 Correct 880 ms 85360 KB Output is correct
13 Correct 784 ms 85564 KB Output is correct
14 Correct 2 ms 5328 KB Output is correct
15 Correct 3 ms 6736 KB Output is correct
16 Correct 3 ms 6864 KB Output is correct
17 Correct 103 ms 64876 KB Output is correct
18 Correct 128 ms 66592 KB Output is correct
19 Correct 125 ms 66160 KB Output is correct
20 Correct 64 ms 85544 KB Output is correct
21 Correct 75 ms 85024 KB Output is correct
22 Correct 110 ms 64932 KB Output is correct
23 Correct 133 ms 66196 KB Output is correct
24 Correct 126 ms 65824 KB Output is correct
25 Correct 61 ms 85536 KB Output is correct
26 Correct 67 ms 83396 KB Output is correct
27 Correct 5 ms 6480 KB Output is correct
28 Correct 4 ms 6480 KB Output is correct
29 Correct 5 ms 6480 KB Output is correct
30 Correct 4 ms 6924 KB Output is correct
31 Correct 3 ms 6736 KB Output is correct
32 Correct 4 ms 6496 KB Output is correct
33 Correct 4 ms 6480 KB Output is correct
34 Correct 4 ms 6480 KB Output is correct
35 Correct 3 ms 6864 KB Output is correct
36 Correct 4 ms 6736 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 19672 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 3 ms 5456 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 4 ms 6436 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 4 ms 6500 KB Output is correct
7 Correct 4 ms 6480 KB Output is correct
8 Incorrect 3 ms 6864 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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