답안 #791164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791164 2023-07-23T13:32:29 Z kshitij_sodani Fire (JOI20_ho_t5) C++14
6 / 100
872 ms 74112 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,llo i){
	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,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()){
		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,j);
			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 8 ms 19156 KB Output is correct
2 Incorrect 8 ms 19248 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 19156 KB Output is correct
2 Correct 787 ms 74084 KB Output is correct
3 Correct 700 ms 73944 KB Output is correct
4 Incorrect 872 ms 74112 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 19156 KB Output is correct
2 Incorrect 724 ms 71856 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 619 ms 57340 KB Output is correct
2 Correct 606 ms 57204 KB Output is correct
3 Correct 601 ms 57728 KB Output is correct
4 Correct 613 ms 57500 KB Output is correct
5 Correct 655 ms 57604 KB Output is correct
6 Correct 684 ms 57392 KB Output is correct
7 Correct 683 ms 57676 KB Output is correct
8 Correct 749 ms 57588 KB Output is correct
9 Correct 642 ms 57468 KB Output is correct
10 Correct 695 ms 57552 KB Output is correct
11 Correct 636 ms 57516 KB Output is correct
12 Correct 711 ms 57584 KB Output is correct
13 Correct 731 ms 57524 KB Output is correct
14 Correct 659 ms 57704 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 19156 KB Output is correct
2 Incorrect 8 ms 19248 KB Output isn't correct
3 Halted 0 ms 0 KB -