답안 #791229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791229 2023-07-23T18:39:27 Z kshitij_sodani Fire (JOI20_ho_t5) C++14
6 / 100
848 ms 74204 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]].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<<su<<",,,,"<<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});
	}
	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:146: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]
  146 |   if(low+(1<<ii)<tt.size()){
      |      ~~~~~~~~~~~^~~~~~~~~~
ho_t5.cpp:161: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]
  161 |  if(low+1<tt.size()){
      |     ~~~~~^~~~~~~~~~
ho_t5.cpp:164: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]
  164 |    if(xx+(1<<jj)<tt.size()){
      |       ~~~~~~~~~~^~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:223: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]
  223 |  for(llo i=0;i<tt.size();i++){
      |              ~^~~~~~~~~~
ho_t5.cpp: In function 'void setIO(std::string)':
ho_t5.cpp:183:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |  freopen((name+".txt").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 19156 KB Output is correct
2 Incorrect 9 ms 19156 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 19156 KB Output is correct
2 Correct 832 ms 74052 KB Output is correct
3 Correct 617 ms 73736 KB Output is correct
4 Incorrect 848 ms 74204 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 19156 KB Output is correct
2 Incorrect 702 ms 72004 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 604 ms 57368 KB Output is correct
2 Correct 624 ms 58100 KB Output is correct
3 Correct 607 ms 58624 KB Output is correct
4 Correct 616 ms 58392 KB Output is correct
5 Correct 625 ms 58536 KB Output is correct
6 Correct 615 ms 58292 KB Output is correct
7 Correct 605 ms 58568 KB Output is correct
8 Correct 629 ms 58520 KB Output is correct
9 Correct 617 ms 58436 KB Output is correct
10 Correct 666 ms 58448 KB Output is correct
11 Correct 608 ms 58408 KB Output is correct
12 Correct 604 ms 58476 KB Output is correct
13 Correct 604 ms 58420 KB Output is correct
14 Correct 630 ms 58640 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 19156 KB Output is correct
2 Incorrect 9 ms 19156 KB Output isn't correct
3 Halted 0 ms 0 KB -