oj.uz

Submission #464796

# Submission time Handle Problem Language Result Execution time Memory
464796 2021-08-14T07:21:09 Z jamezzz Dungeon 3 (JOI21_ho_t5) C++17
11 / 100
 665 ms 67496 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define maxn 200005

int n,q,a[maxn],b[maxn],s,t,u,r[maxn];
ll x[maxn],ans[maxn];
vi disc;
stack<int> st;

int get(int i){
	return upper_bound(all(disc),i)-disc.begin();
}

struct query{
	int u,i,mult;
};

vector<query> qrys[maxn];

struct maxseg{
	int s,e,m,v;maxseg *l,*r;
	maxseg(int _s,int _e){
		s=_s;e=_e;m=(s+e)>>1;v=0;
		if(s!=e)l=new maxseg(s,m),r=new maxseg(m+1,e);
	}
	void up(int x,int nv){
		if(s==x&&e==x){ v=nv;return; }
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
		v=max(l->v,r->v);
	}
	int qry(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return max(l->qry(x,m),r->qry(m+1,y));
	}
}*die;

struct minseg{
	int s,e,m;ii v;minseg *l,*r;
	minseg(int _s,int _e){
		s=_s;e=_e;m=(s+e)>>1;v={0,0};
		if(s!=e)l=new minseg(s,m),r=new minseg(m+1,e);
	}
	void up(int x,ii nv){
		if(s==x&&e==x){ v=nv;return; }
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
		v=min(l->v,r->v);
	}
	ii qry(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return min(l->qry(x,m),r->qry(m+1,y));
	}
}*getmin;

struct fw{
	ll ft[maxn];
	void init(){
		for(int i=1;i<=n+1;++i){
			ft[i]=0;
		}
	}
	void up(int x,int y,ll v){
		while(x<=n+1){
			ft[x]+=v;x+=x&-x;
		}
		++y;
		while(y<=n+1){
			ft[y]-=v;y+=y&-y;
		}
	}
	ll qry(int x){
		ll res=0;
		while(x){
			res+=ft[x];x-=x&-x;
		}
		return res;
	}
}*m=new fw(),*c=new fw();

int main(){
	sf("%d%d",&n,&q);
	
	die=new maxseg(1,n+1);
	getmin=new minseg(1,n+1);
	
	for(int i=1;i<=n;++i){
		sf("%d",&a[i]);
		die->up(i+1,a[i]);//max jump
		x[i+1]=x[i]+a[i];
	}
	for(int i=1;i<=n;++i){
		sf("%d",&b[i]);
		getmin->up(i,{b[i],i});
	}
	
	for(int i=0;i<q;++i){
		sf("%d%d%d",&s,&t,&u);
		if(die->qry(s+1,t)>u){
			//max distance is more than u, impossible
			ans[i]=-1;
		}
		else{
			qrys[s].pb({u,i,1});
			
			//answer is cost from s to n+1 - cost from minpos to n+1 + 
			//cost to get from minpos to t, buying from minpos
			int leftpos=lower_bound(x+1,x+n+1,x[t]-u)-x;
			int minpos=getmin->qry(max(s,leftpos),t-1).se;
			ans[i]=(x[t]-x[minpos])*b[minpos];
			qrys[minpos].pb({u,i,-1});
			
			disc.pb(u);
		}
	}
	
	disc.pb(INF);
	sort(all(disc));
	disc.erase(unique(all(disc)),disc.end());

	m->init();c->init();
	b[n+1]=-INF;st.push(n+1);
	
	for(int i=n;i>=1;--i){
		while(b[st.top()]>=b[i]){
			int j=st.top();st.pop();
			
			int dl=get(x[j]-x[i]);
			int dr=get(x[r[j]]-x[i]);
			
			m->up(dl+1,dr,-b[j]);
			c->up(dl+1,dr,(x[j]-x[i])*b[j]);
			c->up(dr+1,maxn-1,-(x[r[j]]-x[j])*b[j]);
		}
		
		r[i]=st.top();
		int d=get(x[r[i]]-x[i]);
		m->up(1,d,b[i]);//x<d:y=b[i]*x
		c->up(d+1,maxn-1,(x[r[i]]-x[i])*b[i]);//x>=d:y=d*b[i]
		
		st.push(i);
		
		for(query q:qrys[i]){
			ans[q.i]+=q.mult*(q.u*m->qry(get(q.u))+c->qry(get(q.u)));
		}
	}
	
	for(int i=0;i<q;++i){
		pf("%lld\n",ans[i]);
	}
}

/*
5 4
3 4 1 1 4
2 5 1 2 1
1 6 3
1 6 4
3 5 1
2 5 9
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:114:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  sf("%d%d",&n,&q);
      |    ^
Main.cpp:120:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |   sf("%d",&a[i]);
      |     ^
Main.cpp:125:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |   sf("%d",&b[i]);
      |     ^
Main.cpp:130:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   sf("%d%d%d",&s,&t,&u);
      |     ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9036 KB Output is correct
2 Correct 12 ms 8984 KB Output is correct
3 Correct 12 ms 8940 KB Output is correct
4 Correct 12 ms 9036 KB Output is correct
5 Correct 14 ms 9056 KB Output is correct
6 Correct 12 ms 9064 KB Output is correct
7 Correct 12 ms 9132 KB Output is correct
8 Correct 14 ms 9068 KB Output is correct
9 Correct 12 ms 9084 KB Output is correct
10 Correct 11 ms 9020 KB Output is correct
11 Correct 11 ms 9016 KB Output is correct
12 Correct 13 ms 9060 KB Output is correct
13 Correct 11 ms 9036 KB Output is correct
14 Correct 12 ms 9072 KB Output is correct
15 Correct 11 ms 8956 KB Output is correct
16 Correct 11 ms 9036 KB Output is correct
17 Correct 11 ms 8996 KB Output is correct
18 Correct 11 ms 9056 KB Output is correct
19 Correct 11 ms 9060 KB Output is correct
20 Correct 11 ms 8976 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 23524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 665 ms 67496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9036 KB Output is correct
2 Correct 12 ms 8984 KB Output is correct
3 Correct 12 ms 8940 KB Output is correct
4 Correct 12 ms 9036 KB Output is correct
5 Correct 14 ms 9056 KB Output is correct
6 Correct 12 ms 9064 KB Output is correct
7 Correct 12 ms 9132 KB Output is correct
8 Correct 14 ms 9068 KB Output is correct
9 Correct 12 ms 9084 KB Output is correct
10 Correct 11 ms 9020 KB Output is correct
11 Correct 11 ms 9016 KB Output is correct
12 Correct 13 ms 9060 KB Output is correct
13 Correct 11 ms 9036 KB Output is correct
14 Correct 12 ms 9072 KB Output is correct
15 Correct 11 ms 8956 KB Output is correct
16 Correct 11 ms 9036 KB Output is correct
17 Correct 11 ms 8996 KB Output is correct
18 Correct 11 ms 9056 KB Output is correct
19 Correct 11 ms 9060 KB Output is correct
20 Correct 11 ms 8976 KB Output is correct
21 Incorrect 168 ms 23524 KB Output isn't correct
22 Halted 0 ms 0 KB -