oj.uz

답안 #782285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
782285 2023-07-13T18:32:41 Z FEDIKUS 송신탑 (IOI22_towers) C++17
14 / 100
 1022 ms 85568 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;
	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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 475 ms 50676 KB 9th lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5456 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 4 ms 6480 KB Output is correct
4 Correct 4 ms 6432 KB Output is correct
5 Correct 4 ms 6416 KB Output is correct
6 Correct 4 ms 6480 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5456 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 4 ms 6480 KB Output is correct
4 Correct 4 ms 6432 KB Output is correct
5 Correct 4 ms 6416 KB Output is correct
6 Correct 4 ms 6480 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

# 결과 실행 시간 메모리 Grader output
1 Correct 653 ms 64196 KB Output is correct
2 Correct 852 ms 64856 KB Output is correct
3 Correct 867 ms 64568 KB Output is correct
4 Correct 843 ms 66492 KB Output is correct
5 Correct 924 ms 65728 KB Output is correct
6 Correct 908 ms 66748 KB Output is correct
7 Correct 963 ms 65728 KB Output is correct
8 Correct 961 ms 85536 KB Output is correct
9 Correct 864 ms 85568 KB Output is correct
10 Correct 842 ms 79652 KB Output is correct
11 Correct 1022 ms 79632 KB Output is correct
12 Correct 953 ms 85312 KB Output is correct
13 Correct 915 ms 85556 KB Output is correct
14 Correct 2 ms 5328 KB Output is correct
15 Correct 4 ms 6736 KB Output is correct
16 Correct 3 ms 6864 KB Output is correct
17 Correct 104 ms 64844 KB Output is correct
18 Correct 134 ms 66720 KB Output is correct
19 Correct 124 ms 66112 KB Output is correct
20 Correct 63 ms 85568 KB Output is correct
21 Correct 67 ms 85100 KB Output is correct
22 Correct 110 ms 64932 KB Output is correct
23 Correct 139 ms 66276 KB Output is correct
24 Correct 128 ms 65708 KB Output is correct
25 Correct 61 ms 85568 KB Output is correct
26 Correct 65 ms 83388 KB Output is correct
27 Correct 4 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 3 ms 6864 KB Output is correct
31 Correct 3 ms 6736 KB Output is correct
32 Correct 4 ms 6480 KB Output is correct
33 Correct 6 ms 6480 KB Output is correct
34 Correct 4 ms 6480 KB Output is correct
35 Correct 4 ms 6864 KB Output is correct
36 Correct 4 ms 6736 KB Output is correct

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 211 ms 19648 KB 2nd lines differ - on the 1st token, expected: '7063', found: '7197'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5456 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 4 ms 6480 KB Output is correct
4 Correct 4 ms 6432 KB Output is correct
5 Correct 4 ms 6416 KB Output is correct
6 Correct 4 ms 6480 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 475 ms 50676 KB 9th lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -