Submission #791232

#	Time	Username	Problem	Language	Result	Execution time	Memory
791232		kshitij_sodani	Fire (JOI20_ho_t5)	C++14	1 / 100	1080 ms	262144 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
 
llo n,q;
llo it[200002];
llo pre6[200002];
llo par[200002];
bool vis[200002];
llo fin[200002];
vector<llo> adj[200002];
vector<pair<pair<llo,llo>,llo>> pre[200002];
llo ind[200002];
//llo pre[200002];
vector<llo> pre3[200002];
vector<pair<llo,llo>> tt;
llo ss[200002];
vector<llo> pre4[200002];
llo co=0;
void dfs(llo no){
	vis[no]=1;
	ss[no]=1;
	assert(no==co);
	co++;

	for(auto j:adj[no]){
		tt.pb({no,j});
		par[j]=no;
		dfs(j);
		ss[no]+=ss[j];
		//llo te=j-no;
		pre3[j-no].pb(j);
		pre4[(j-no)+ss[j]].pb(j);
		//time j-no  duration ss[no]
	}
}
llo tree[4*200002][2];
void update(llo no,llo l,llo r,llo i,llo aa,llo bb){
	if(l==r){
		tree[no][0]=aa;
		tree[no][1]=-bb*aa;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i,aa,bb);
		}
		else{
			update(no*2+2,mid+1,r,i,aa,bb);
		}
		tree[no][0]=tree[no*2+1][0]+tree[no*2+2][0];
		tree[no][1]=tree[no*2+1][1]+tree[no*2+2][1];
	}
}
pair<llo,llo>  query2(llo no,llo l,llo r,llo aa,llo bb){
	if(r<aa or l>bb or aa>bb){
		return {0,0};
	}
	if(aa<=l and r<=bb){
		return {tree[no][0],tree[no][1]};
	}
	llo mid=(l+r)/2;
	pair<llo,llo> x=query2(no*2+1,l,mid,aa,bb);
	pair<llo,llo> y=query2(no*2+2,mid+1,r,aa,bb);
	return {x.a+y.a,x.b+y.b};
}
vector<pair<int,int>> tree2[4*200002];
vector<llo> tree3[4*200002][2];
vector<int> ind2[4*200002];
void build(llo no,llo l,llo r){
	for(llo j=l;j<=r;j++){
		if(tt.size()<=j){
			continue;
		}
		tree2[no].pb({tt[j].b,j-l});
	}
	sort(tree2[no].begin(),tree2[no].end());
	for(llo j=1;j<=r-l+2;j++){
		tree3[no][0].pb(0);
		tree3[no][1].pb(0);
		ind2[no].pb(-1);
	}
	for(llo j=0;j<tree2[no].size();j++){
		ind2[no][tree2[no][j].b]=j;
	}
	if(l<r){
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
	}
}
void uu(llo no,llo i,pair<llo,llo> x){
	while(i<tree3[no][0].size()){
		tree3[no][0][i]+=x.a;
		tree3[no][1][i]+=x.b;
		i+=(i&-i);
	}
}
pair<llo,llo> s2(llo no,llo i){
	llo su=0;
	llo su2=0;
	while(i>0){
		su+=tree3[no][0][i];
		su2+=tree3[no][1][i];
		i-=(i&-i);

	}
	return {su,su2};
}
void update3(llo no,llo l,llo r,llo i,pair<llo,llo> x){
	llo xa=ind2[no][i-l];
	//cout<<xa<<"::"<<endl;

	/*if(i==3){
		cout<<x.a<<"???????????????"<<xa<<endl;
	}*/
	uu(no,xa+1,x);
	if(l<r){
		llo mid=(l+r)/2;
		if(i<=mid){
			update3(no*2+1,l,mid,i,x);
		}
		else{
			update3(no*2+2,mid+1,r,i,x);
		}
	}
}
pair<llo,llo> query3(llo no,llo l,llo r,llo aa,llo bb,llo i){
	if(r<aa or l>bb or aa>bb){
		return {0,0};
	}
	if(aa<=l and r<=bb){
		llo low=-1;
	/*	if(3>=l and 3<=r){
			cout<<l<<"<"<<r<<endl;
			for(auto jj:tree2[no]){
				cout<<jj.a<<";;"<<jj.b<<endl;
			}
		}*/
		for(llo j=19;j>=0;j--){
			if(low+(1<<j)<tree2[no].size()){
				if(tree2[no][low+(1<<j)].a<=i){
					low+=(1<<j);
				}
			}
		}
	/*	if(3>=l and 3<=r){
			cout<<low<<"//"<<s2(no,low+1).a<<endl;
		}*/
		return s2(no,low+1);
	}
	else{
		llo mid=(l+r)/2;
		pair<llo,llo> xx=query3(no*2+1,l,mid,aa,bb,i);
		pair<llo,llo> yy=query3(no*2+2,mid+1,r,aa,bb,i);
		return {xx.a+yy.a,xx.b+yy.b};
	}
}
llo tree4[4*200002];
llo lazy[4*200002];
void push(llo no,llo l,llo r){
	tree4[no]+=lazy[no]*(r-l+1);
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
}
void update2(llo no,llo l,llo r,llo aa,llo bb,llo x){
	push(no,l,r);
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		lazy[no]=x;
		push(no,l,r);
	}
	else{
		llo mid=(l+r)/2;
		update2(no*2+1,l,mid,aa,bb,x);
		update2(no*2+2,mid+1,r,aa,bb,x);
		tree4[no]=tree4[no*2+1]+tree4[no*2+2];
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb){
	push(no,l,r);
	if(r<aa or l>bb or aa>bb){
		return 0;
	}
	if(aa<=l and r<=bb){
		return tree4[no];
	}
	llo mid=(l+r)/2;
	llo x=query(no*2+1,l,mid,aa,bb);
	llo y=query(no*2+2,mid+1,r,aa,bb);
	//tree4[no]=tree4[no*2+1]+tree4[no*2+2];
	return x+y;
}
llo solve(llo i,llo j){
	llo low=-1;
	for(llo ii=19;ii>=0;ii--){
		if(low+(1<<ii)<tt.size()){
			if(tt[low+(1<<ii)].a<j-i){
				low+=(1<<ii);
			}
		}
	}
	llo su=0;
	if(low>=0){
		pair<llo,llo> xx=query2(0,0,n-1,0,low);
	//	cout<<xx.a<<"????"<<endl;
		su+=xx.b;
		su+=xx.a*(i+1);
		//cout<<su<<",,,"<<endl;
	}
	//cout<<low<<"??"<<endl;
	if(low+1<tt.size()){
		pair<llo,llo> yy=query3(0,0,n-1,low+1,n-1,j);
		su+=yy.b;
		su+=(j+1)*yy.a;
	}
	return su;
}
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".txt").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//setIO("02-02");
	cin>>n>>q;
	vector<pair<llo,llo>> ss5;
	for(llo i=0;i<n;i++){
	    ///it[i]=n-i-1;
		cin>>it[i];
		pre6[i+1]=pre6[i]+it[i];
		while(ss5.size()){
			if(ss5.back().a<=it[i]){
				ss5.pop_back();
			}
			else{
				break;
			}
		}
		if(ss5.size()){
			adj[ss5.back().b].pb(i);
		}
		ss5.pb({it[i],i});
	}

	for(llo i=0;i<n;i++){
		if(vis[i]==0){
			dfs(i);
			par[i]=-1;

		}
	}
	
	sort(tt.begin(),tt.end());
	/*for(int i=0;i+1<tt.size();i++){
		assert(tt[i].b<=tt[i+1].b);
	}*/
	
	for(llo i=0;i<tt.size();i++){
		ind[tt[i].b]=i;
	}

	for(llo ii=0;ii<q;ii++){
		llo t,l,r;
		cin>>t>>l>>r;
		l--;
		r--;
		pre[t].pb({{l,r},ii});
	}
	build(0,0,n-1);

	for(llo i=1;i<=n;i++){
		//cout<<i<<":"<<endl;
		for(auto j:pre3[i]){
		//	cout<<j<<",,"<<ind[j]<<endl;
			llo x=it[par[j]]-it[j];
		//	cout<<j<<"+"<<endl;
			update(0,0,n-1,ind[j],x,i);

			update3(0,0,n-1,ind[j],{x,-j*x});
		}

		for(auto j:pre4[i]){
		//	cout<<j<<"-"<<endl;
		//cout<<j<<"?"<<j+ss[j]-1<<"?"<<it[par[j]]-it[j]<<endl;
			update2(0,0,n-1,j,j+ss[j]-1,it[par[j]]-it[j]);
			update(0,0,n-1,ind[j],0,0);
			llo x=it[par[j]]-it[j];
			update3(0,0,n-1,ind[j],{-x,j*x});
		}
		for(auto jj:pre[i]){
			pair<llo,llo> j=jj.a;
			llo cur=pre6[j.b+1]-pre6[j.a];
			//cout<<cur<<"::"<<endl;
			cur+=query(0,0,n-1,j.a,j.b);
			//continue;
			//cout<<cur<<",,"<<endl;///<<tree4[0]<<endl;
			cur+=solve(i,j.b);
			if(j.a>0){
				cur-=solve(i,j.a-1);
			}
			fin[jj.b]=cur;

		}
	}


	for(llo i=0;i<q;i++){
		cout<<fin[i]<<endl;
	}

 
	
 
 
	return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'void build(llo, llo, llo)':
ho_t5.cpp:76:15: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'llo' {aka 'long long int'} [-Wsign-compare]
   76 |   if(tt.size()<=j){
      |      ~~~~~~~~~^~~
ho_t5.cpp:87:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(llo j=0;j<tree2[no].size();j++){
      |              ~^~~~~~~~~~~~~~~~~
ho_t5.cpp: In function 'void uu(llo, llo, std::pair<long long int, long long int>)':
ho_t5.cpp:97:9: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  while(i<tree3[no][0].size()){
      |        ~^~~~~~~~~~~~~~~~~~~~
ho_t5.cpp: In function 'std::pair<long long int, long long int> query3(llo, llo, llo, llo, llo, llo)':
ho_t5.cpp:145:17: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    if(low+(1<<j)<tree2[no].size()){
      |       ~~~~~~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp: In function 'llo solve(llo, llo)':
ho_t5.cpp:206:17: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |   if(low+(1<<ii)<tt.size()){
      |      ~~~~~~~~~~~^~~~~~~~~~
ho_t5.cpp:221:10: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |  if(low+1<tt.size()){
      |     ~~~~~^~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:271:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |  for(llo i=0;i<tt.size();i++){
      |              ~^~~~~~~~~~
ho_t5.cpp: In function 'void setIO(std::string)':
ho_t5.cpp:230:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  230 |  freopen((name+".txt").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t5.cpp:231:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80