제출 #803703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
803703		kshitij_sodani	송신탑 (IOI22_towers)	C++17	0 / 100	4057 ms	5200 KiB

towers

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#include "towers.h"

#include <vector>
int st=0;
int n;
vector<int> it;
int tree[4*200001][2];
void build(int no,int l,int r){
	if(l==r){
		tree[no][0]=it[l];
		tree[no][1]=it[l];
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no][0]=min(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
	}
}
int query(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return 1e9+1;
	}
	if(aa<=l and r<=bb){
		return tree[no][0];
	}
	int mid=(l+r)/2;
	return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
int query2(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return -1;
	}
	if(aa<=l and r<=bb){
		return tree[no][1];
	}
	int mid=(l+r)/2;
	return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb));
}
vector<pair<int,int>> mm;

void init(int nn, vector<int> ita) {
	n=nn;
	it=ita;
	st=0;
	build(0,0,n-1);
	
}
int le[100001];
int re2[100001];
void rec(int l,int r){
	mm.clear();
	vector<pair<llo,llo>> ss;
	for(int i=r;i>=l;i--){
		while(ss.size()){
			if(ss.back().a<it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		re2[i]=n-1;
		if(ss.size()){
			re2[i]=ss.back().b-1;
		}
		ss.pb({it[i],i});
	}
	ss.clear();
	for(int i=l;i<=r;i++){
		while(ss.size()){
			if(ss.back().a<it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		le[i]=0;
		if(ss.size()){
			le[i]=ss.back().b+1;
		}
		ss.pb({it[i],i});
	}
	for(int i=0;i<n;i++){
		int x=it[i]-query(0,0,n-1,le[i],i);
		int y=it[i]-query(0,0,n-1,i,re2[i]);
		mm.pb({0,min(x,y)});
	}
}
int re[100001][2];
int par[200001][20];
set<pair<int,int>> xx[2];
vector<pair<pair<int,int>,int>> yy;
map<int,int> kk;
int max_towers(int l, int r, int d) {
	int ans=0;
	rec(l,r);

	for(auto j:mm){
		if(d>=j.a and d<=j.b){
			ans++;
		}
	}
	return ans+1;

	if(kk.find(d)==kk.end()){
		llo ind=n;
		kk[d]++;

		yy.clear();
		xx[0].clear();
		xx[1].clear();

		for(int i=n-1;i>=0;i--){
			llo cur=query(0,0,n-1,i+1,ind-1);
			if(cur<=it[i]-d){
				llo zz=ind-1;
				while(zz>i){
					zz--;
					if(query(0,0,n-1,i+1,zz)<=it[i]-d){
						continue;
					}
					else{
						zz++;
						break;
					}
				}
				xx[0].insert({i,yy.size()});
				yy.pb({{i,zz},0});
				re[i][0]=zz;
				ind=zz;
			}
			else{
				re[i][0]=-1;
			}
		}
		ind=n;
		for(int i=n-1;i>=0;i--){
			llo cur=query2(0,0,n-1,i+1,ind-1);
			if(cur>=it[i]+d){
				llo zz=ind-1;
				while(zz>i){
					zz--;
					if(query2(0,0,n-1,i+1,zz)>=it[i]+d){
						continue;
					}
					else{
						zz++;
						break;
					}
				}
				re[i][1]=zz;
				xx[1].insert({i,yy.size()});
				yy.pb({{i,zz},1});
				ind=zz;
			}
			else{
				re[i][1]=-1;
			}
		}
		for(int i=0;i<yy.size();i++){
			par[i][0]=-1;
			auto j=xx[1-yy[i].b].lower_bound({yy[i].a.b,-1});
			if(j!=xx[1-yy[i].b].end()){
				par[i][0]=(*j).b;
			//	cout<<i<<":"<<(*j).b<<endl;
			}
		}
		for(int j=1;j<20;j++){
			for(int i=0;i<yy.size();i++){
				if(par[i][j-1]==-1){
					par[i][j]=-1;
				}
				else{
					par[i][j]=par[par[i][j-1]][j-1];
				}
			}
		}
	/*	for(auto j:yy){
			cout<<j.a.a<<","<<j.a.b<<","<<j.b<<endl;
		}
*/
		st=1;
	}
//	cout<<l<<",,,,"<<-1<<endl;
/*	for(auto j:xx[1]){
		cout<<j.a<<"//"<<j.b<<endl;
	}*/
	auto j=xx[1].lower_bound({l,-1});
	if(j==xx[1].end()){
		return 1;
	}
	int cot=(*j).b;
	//cout<<cot<<":::::"<<yy[cot].a.b<<endl;
//	cout<<((*j).a)<<"<<"<<endl;
	if(yy[cot].a.b>r){
		return 1;
	}
	//cout<<22<<endl;
	int su=1;
//cout<<cot<<";;"<<endl;
	//cout<<par[cot][0]<<":"<<par[cot][1]<<":"<<par[cot][2]<<endl;
	//cout<<par[cot][0]<<";;"<<yy[par[cot][0]].a.b<<";;"<<endl;
	for(int j=19;j>=0;j--){
		if(par[cot][j]>=0){
		//	cout<<yy[par[cot][j]].a.b<<";"<<j<<endl;
			if(yy[par[cot][j]].a.b<=r){
				cot=par[cot][j];
				su+=(1<<j);
			}
		}
	}
	//cout<<su<<",,,,"<<endl;
    return ((su)/2)+1;
}

컴파일 시 표준 에러 (stderr) 메시지

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:169:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |   for(int i=0;i<yy.size();i++){
      |               ~^~~~~~~~~~
towers.cpp:178:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |    for(int i=0;i<yy.size();i++){
      |                ~^~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23