답안 #791165

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791165 2023-07-23T13:33:07 Z kshitij_sodani Fire (JOI20_ho_t5) C++14
6 / 100
998 ms 74264 KB
#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]-1].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};
}
llo tree3[4*200002][2];
void update3(llo no,llo l,llo r,llo i,pair<llo,llo> x){
	if(l==r){
		tree3[no][0]+=x.a;
		tree3[no][1]+=x.b;
	}
	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);
		}
		tree3[no][0]=tree3[no*2+1][0]+tree3[no*2+2][0];
		tree3[no][1]=tree3[no*2+1][1]+tree3[no*2+2][1];
	}
}
pair<llo,llo> query3(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 {tree3[no][0],tree3[no][1]};
	}
	else{
		llo mid=(l+r)/2;
		pair<llo,llo> xx=query3(no*2+1,l,mid,aa,bb);
		pair<llo,llo> yy=query3(no*2+2,mid+1,r,aa,bb);
		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()){
		llo xx=low;
		for(llo jj=19;jj>=0;jj--){
			if(xx+(1<<jj)<tt.size()){
				if(tt[xx+(1<<jj)].b<=j){
					xx+=(1<<jj);
				}
			}
		}
		//cout<<low+1<<"::"<<xx<<endl;
		if(low+1<=xx){
			pair<llo,llo> yy=query3(0,0,n-1,low+1,xx);
			su+=yy.b;
			su+=(j+1)*yy.a;
		}
	//	cout<<yy.a<<",,"<<yy.b<<endl;
	}
	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;

		}
	}
	for(int i=0;i+1<tt.size();i++){
		assert(tt[i].b<=tt[i+1].b);

	}
//	sort(tt.begin(),tt.end());
	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});
	/*	if(tt.size()==0){

			cout<<pre6[r+1]-pre6[l]<<endl;

		}*/
	}
/*	if(tt.size()==0){
		return 0;
	}*/
	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

ho_t5.cpp: In function 'llo solve(llo, llo)':
ho_t5.cpp:148: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]
  148 |   if(low+(1<<ii)<tt.size()){
      |      ~~~~~~~~~~~^~~~~~~~~~
ho_t5.cpp:163: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]
  163 |  if(low+1<tt.size()){
      |     ~~~~~^~~~~~~~~~
ho_t5.cpp:166: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]
  166 |    if(xx+(1<<jj)<tt.size()){
      |       ~~~~~~~~~~^~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:219:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |  for(int i=0;i+1<tt.size();i++){
      |              ~~~^~~~~~~~~~
ho_t5.cpp:224: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]
  224 |  for(llo i=0;i<tt.size();i++){
      |              ~^~~~~~~~~~
ho_t5.cpp: In function 'void setIO(std::string)':
ho_t5.cpp:184:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |  freopen((name+".txt").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t5.cpp:185:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Incorrect 11 ms 19156 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 803 ms 74128 KB Output is correct
3 Correct 698 ms 73724 KB Output is correct
4 Incorrect 998 ms 74264 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Incorrect 771 ms 71856 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 683 ms 57340 KB Output is correct
2 Correct 681 ms 57212 KB Output is correct
3 Correct 654 ms 57736 KB Output is correct
4 Correct 634 ms 57624 KB Output is correct
5 Correct 670 ms 57600 KB Output is correct
6 Correct 691 ms 57400 KB Output is correct
7 Correct 703 ms 57680 KB Output is correct
8 Correct 645 ms 57652 KB Output is correct
9 Correct 610 ms 57464 KB Output is correct
10 Correct 689 ms 57564 KB Output is correct
11 Correct 711 ms 57524 KB Output is correct
12 Correct 645 ms 57580 KB Output is correct
13 Correct 717 ms 57524 KB Output is correct
14 Correct 734 ms 57712 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Incorrect 11 ms 19156 KB Output isn't correct
3 Halted 0 ms 0 KB -