제출 #804272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
804272		kshitij_sodani	송신탑 (IOI22_towers)	C++17	23 / 100	4074 ms	83796 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<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];
int cc[100001][20];
int dd[100001][20];
int val[100001];
int tree2[4*200001];
int tree3[4*200001];

void build2(int no,int l,int r){
	if(l==r){
		tree2[no]=le[l];
		tree3[no]=re2[l];
	}
	else{
		int mid=(l+r)/2;
		build2(no*2+1,l,mid);
		build2(no*2+2,mid+1,r);
		tree2[no]=min(tree2[no*2+1],tree2[no*2+2]);
		tree3[no]=max(tree3[no*2+1],tree3[no*2+2]);
	}
}
int find(int no,int l,int r,int aa,int bb,int x){
	//find first with val less than x
	if(r<aa or l>bb or aa>bb){
		return -1;
	}
	if(l==r){
		if(tree2[no]<x){
			return l;
		}
		return -1;
	}
	if(tree2[no]>=x){
		return -1;
	}
	int mid=(l+r)/2;
	int xx=find(no*2+1,l,mid,aa,bb,x);
	if(xx>=0){
		return xx;
	}
	return find(no*2+2,mid+1,r,aa,bb,x);
}
int find2(int no,int l,int r,int aa,int bb,int x){
	//find first with val less than x
	if(r<aa or l>bb or aa>bb){
		return -1;
	}
	if(l==r){
		if(tree3[no]>x){
			return l;
		}
		return -1;
	}
	if(tree3[no]<=x){
		return -1;
	}
	int mid=(l+r)/2;
	int xx=find2(no*2+2,mid+1,r,aa,bb,x);
	if(xx>=0){
		return xx;
	}
	return find2(no*2+1,l,mid,aa,bb,x);
}
vector<int> adj[100001];
set<int> xa;
vector<pair<int,int>> yy;
int cot[100001*100];
int ll[100001*100];
int rr[100001*100];
int ba[100001];
int ne=0;
int update(int no,int l,int r,int i,int x){
	if(l==r){
		int sta=ne;
		ne++;
		ll[sta]=-1;
		rr[sta]=-1;
		cot[sta]=cot[no]+x;
		return sta;
	}
	else{
		int mid=(l+r)/2;
		int sta=ne;
		ne++;
		if(i<=mid){
			rr[sta]=rr[no];
			if(ll[no]==-1){
				ll[no]=ne;
				ne++;
				ll[ll[no]]=-1;
				rr[ll[no]]=-1;
				cot[ll[no]]=0;
			}
			ll[sta]=update(ll[no],l,mid,i,x);
		}
		else{
			ll[sta]=ll[no];

			if(rr[no]==-1){
				rr[no]=ne;
				ne++;
				rr[rr[no]]=-1;
				ll[rr[no]]=-1;
				cot[rr[no]]=0;
			}
			rr[sta]=update(rr[no],mid+1,r,i,x);
		}
		cot[sta]=0;
		if(ll[sta]>=0){
			cot[sta]+=cot[ll[sta]];
		}
		if(rr[sta]>=0){
			cot[sta]+=cot[rr[sta]];
		}
		return sta;
	}
}
int query5(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return 0;
	}
	if(aa<=l and r<=bb){
		return cot[no];
	}
	int mid=(l+r)/2;
	int su=0;
	if(ll[no]>=0){
		su+=query5(ll[no],l,mid,aa,bb);
	}
	if(rr[no]>=0){
		su+=query5(rr[no],mid+1,r,aa,bb);
	}
	return su;
}	
void dfs(int no,int par=-1){
	if(par==-1){
		par=ne;
		ll[ne]=-1;
		rr[ne]=-1;
		ne++;
	}
	else{
	}
	if(par!=-1){
		ba[no]=update(par,0,n-1,val[no],1);
	}
	else{
		ba[no]=par;

	}
	for(auto j:adj[no]){
		dfs(j,ba[no]);
	}
}
vector<int> adj2[100001];
int ba2[100001];
void dfs2(int no,int par=-1){
	if(par==-1){
		par=ne;
		ll[ne]=-1;
		rr[ne]=-1;
		ne++;
	}
	else{
	}
	if(par!=-1){
		ba2[no]=update(par,0,n-1,val[no],1);
	}
	else{
		ba2[no]=par;
	}
	for(auto j:adj2[no]){
		dfs2(j,ba2[no]);
	}
}
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;
		if(ss.size()){
			re2[i]=ss.back().b;
		}
		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]=-1;
		if(ss.size()){
			le[i]=ss.back().b;
		}
		ss.pb({it[i],i});
	}
	for(int i=0;i<n;i++){
		int x=it[i]-query(0,0,n-1,le[i]+1,i);
		int y=it[i]-query(0,0,n-1,i,re2[i]-1);
		val[i]=min(x,y);
		xa.insert(val[i]);
		mm.pb(min(x,y));
	}
	int ind7=0;
	map<int,int> kk;
	for(auto j:xa){
		kk[j]=ind7;
		yy.pb({j,ind7});
		ind7++;
	}
	for(int i=0;i<n;i++){
		val[i]=kk[val[i]];
	}
	

	for(int i=0;i<n;i++){
		cc[i][0]=le[i];
		dd[i][0]=re2[i];
		adj[dd[i][0]].pb(i);
		if(cc[i][0]==-1){
			adj2[n].pb(i);
		}
		else{
			adj2[cc[i][0]].pb(i);
		}
	//	cout<<i<<":"<<le[i]<<endl;
	//	cout<<i<<":"<<re2[i]<<endl;
		if(re2[i]==n){
			dd[i][0]=-1;
		}
	}
	dfs(n);
	dfs2(n);

	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(cc[i][j-1]==-1){
				cc[i][j]=-1;
			}
			else{
				cc[i][j]=cc[cc[i][j-1]][j-1];
			}
		}
	}
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(dd[i][j-1]==-1){
				dd[i][j]=-1;
			}
			else{
				dd[i][j]=dd[dd[i][j-1]][j-1];
			}
		}
	}
	build2(0,0,n-1);
	sort(mm.begin(),mm.end());

}

int max_towers(int l, int r, int d) {
	if(st==0){
		rec(0,n-1);
		st=1;
	}
	int de=yy.size();

	for(int j=19;j>=0;j--){
		if(de-(1<<j)>=0){
			if(yy[de-(1<<j)].a>=d){
				de-=(1<<j);
			}
		}	
	}

	if(de==yy.size()){
		return 1;
	}
	
	llo low=mm.size();
	llo su=0;
	for(int i=l;i<=r;i++){
		if(val[i]>=de){
			su++;
		}
	}
	int ind=find(0,0,n-1,l,r,l);

	int ind2=ind;
	for(int j=19;j>=0;j--){
		if(dd[ind2][j]<=r and dd[ind2][j]>=0){
			ind2=dd[ind2][j];
		}
	}
	vector<llo> ss;
	int ind3=-1;
	if(query(0,0,n-1,l,ind-1)>it[ind]-d){
		ind3=ind;
		for(int j=19;j>=0;j--){
			if(dd[ind][j]<=r and dd[ind][j]>=0){
				if(query(0,0,n-1,l,dd[ind][j]-1)>it[dd[ind][j]]-d){
					ind=dd[ind][j];
				}
			}
		}		
		llo zot=query5(ba[ind3],0,n-1,de,n-1);
		zot-=query5(ba[re2[ind]],0,n-1,de,n-1);
		su-=zot;
		ss.pb(ind);

	}

	pair<int,int> ll={ind3,ind};

	//from ind3 to ind
	//return su;
	vector<int> tt;
	ind=-1;
	ind=find2(0,0,n-1,l,r,r);

	ind3=-1;
	if(query(0,0,n-1,ind+1,r)<=it[ind]-d){
	}
	else{
		ind3=ind;
		for(int j=19;j>=0;j--){
			if(cc[ind][j]>=l){
				if(query(0,0,n-1,cc[ind][j]+1,r)>it[cc[ind][j]]-d){
					ind=cc[ind][j];
				}
			}
		}
		llo zot=query5(ba2[ind3],0,n-1,de,n-1);
		if(cc[ind][0]==-1){
			zot-=query5(ba2[n],0,n-1,de,n-1);
		}
		else{
			zot-=query5(ba2[cc[ind][0]],0,n-1,de,n-1);
		}
		su-=zot;

	/*	while(true){
			if(val[ind3]>=de){
				su--;

			}
		//	tt.pb(ind3);
			if(ind3==ind){
				break;
			}
			ind3=cc[ind3][0];
		}*/
	}
	pair<int,int> rr={ind3,ind};
/*	for(auto j:ss){
		if(val[j]>=de){
			su--;
		}
	}*/
/*	for(auto j:tt){
		if(val[j]>=de){
			su--;
		}
	}*/
	if(ll.a>=0 and rr.a>=0){
		if(rr.b==ind2 and ll.b==ind2){
			if(val[rr.b]>=de){
				su--;
			}
		}
	}
	
	su++;
	return su;
}

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

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:344:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  344 |  if(de==yy.size()){
      |     ~~^~~~~~~~~~~
towers.cpp:348:6: warning: unused variable 'low' [-Wunused-variable]
  348 |  llo low=mm.size();
      |      ^~~

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