oj.uz

Submission #978811

# Submission time Handle Problem Language Result Execution time Memory
978811 2024-05-09T17:48:53 Z MilosMilutinovic Fish 3 (JOI24_fish3) C++14
100 / 100
 1398 ms 71108 KB 
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,q;
ll d,c[300005],a[300005],b[300005],val[300005],res[300005],sum[300005],mn[1200005],lzy[1200005],s[1200005],spref[300005];
int pref[300005];
vector<pii> qs[300005];

void pushdown(int id,int l,int r){
	if(lzy[id]==(ll)1e18||l==r) return;
	int mid=(l+r)/2;
	s[id<<1]=lzy[id]*(mid-l+1);
	s[id<<1|1]=lzy[id]*(r-mid);
	lzy[id<<1]=lzy[id];
	lzy[id<<1|1]=lzy[id];
	lzy[id]=(ll)1e18;
	return;
}

void build(int id,int l,int r){
	mn[id]=(ll)1e18;
	lzy[id]=(ll)1e18;
	s[id]=0;
	if(l==r) return;
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	mn[id]=min(mn[id<<1],mn[id<<1|1]);
}

void change(int id,int l,int r,int ql,int qr,ll v){
	if(ql<=l&&r<=qr){
		s[id]=v*(r-l+1);
		lzy[id]=v;
		pushdown(id,l,r);
		return;
	}
	pushdown(id,l,r);
	int mid=(l+r)/2;
	if(qr<=mid) change(id<<1,l,mid,ql,qr,v);
	else if(ql>mid) change(id<<1|1,mid+1,r,ql,qr,v);
	else change(id<<1,l,mid,ql,qr,v),change(id<<1|1,mid+1,r,ql,qr,v);
	s[id]=s[id<<1]+s[id<<1|1];
}

ll query(int id,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return s[id];
	pushdown(id,l,r);
	int mid=(l+r)/2;
	ll ret;
	if(qr<=mid) ret=query(id<<1,l,mid,ql,qr);
	else if(ql>mid) ret=query(id<<1|1,mid+1,r,ql,qr);
	else ret=query(id<<1,l,mid,ql,qr)+query(id<<1|1,mid+1,r,ql,qr);
	s[id]=s[id<<1]+s[id<<1|1];
	return ret;
}

int main(){
	n=readint(); d=readint();
	for(int i=1;i<=n;i++) c[i]=readint();
	q=readint();
	for(int i=1;i<=q;i++){
		int l=readint(),r=readint();
		qs[r].pb(mp(l,i));
	}
	for(int i=1;i<=n;i++){
		a[i]=c[i]/d;
		b[i]=c[i]%d;
		sum[i]=sum[i-1]+a[i];
	}
	build(1,1,n);
	for(int i=2;i<=n;i++) pref[i]=pref[i-1]+(b[i]<b[i-1]?1:0);
	for(int i=2;i<=n;i++) spref[i]=spref[i-1]+pref[i];
	for(int i=1;i<=n;i++){
		int l=1,r=i,p=i;
		while(l<=r){
			int mid=(l+r)/2;
			if(query(1,1,n,mid,mid)+pref[mid]>a[i]-pref[i]+pref[mid]) p=mid,r=mid-1;
			else l=mid+1;
		}
		change(1,1,n,p,i,a[i]-pref[i]);
		for(auto p:qs[i]){
			if(query(1,1,n,p.fi,p.fi)+pref[p.fi]<0){
				res[p.se]=-1;
			}else{
				res[p.se]=sum[i]-sum[p.fi-1];
				res[p.se]-=query(1,1,n,p.fi,i);
				res[p.se]-=spref[i]-spref[p.fi-1];
			}
		}
	}
	for(int i=1;i<=q;i++) printf("%lld\n",res[i]);
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23128 KB Output is correct
2 Correct 4 ms 23132 KB Output is correct
3 Correct 4 ms 23132 KB Output is correct
4 Correct 10 ms 23172 KB Output is correct
5 Correct 9 ms 23432 KB Output is correct
6 Correct 8 ms 23132 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 8 ms 23128 KB Output is correct
9 Correct 12 ms 23132 KB Output is correct
10 Correct 9 ms 23132 KB Output is correct
11 Correct 9 ms 23132 KB Output is correct
12 Correct 12 ms 23132 KB Output is correct
13 Correct 11 ms 21080 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1211 ms 60064 KB Output is correct
2 Correct 1272 ms 63544 KB Output is correct
3 Correct 85 ms 34784 KB Output is correct
4 Correct 1076 ms 63272 KB Output is correct
5 Correct 1077 ms 61588 KB Output is correct
6 Correct 1110 ms 63292 KB Output is correct
7 Correct 1091 ms 63012 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 38708 KB Output is correct
2 Correct 1160 ms 71108 KB Output is correct
3 Correct 1257 ms 70844 KB Output is correct
4 Correct 1282 ms 70860 KB Output is correct
5 Correct 1230 ms 70844 KB Output is correct
6 Correct 1244 ms 64568 KB Output is correct
7 Correct 1174 ms 64584 KB Output is correct
8 Correct 1168 ms 67796 KB Output is correct
9 Correct 1150 ms 67788 KB Output is correct
10 Correct 1286 ms 66224 KB Output is correct
11 Correct 1252 ms 66228 KB Output is correct
12 Correct 1239 ms 69296 KB Output is correct
13 Correct 1274 ms 69292 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1223 ms 54780 KB Output is correct
2 Correct 1213 ms 64324 KB Output is correct
3 Correct 434 ms 46204 KB Output is correct
4 Correct 1355 ms 67552 KB Output is correct
5 Correct 1137 ms 69636 KB Output is correct
6 Correct 1225 ms 70852 KB Output is correct
7 Correct 988 ms 60296 KB Output is correct
8 Correct 1211 ms 70856 KB Output is correct
9 Correct 1125 ms 63600 KB Output is correct
10 Correct 1152 ms 63300 KB Output is correct
11 Correct 1398 ms 67624 KB Output is correct
12 Correct 1195 ms 66784 KB Output is correct
13 Correct 1279 ms 70724 KB Output is correct
14 Correct 1022 ms 66608 KB Output is correct
15 Correct 1315 ms 70596 KB Output is correct
16 Correct 959 ms 66496 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23128 KB Output is correct
2 Correct 4 ms 23132 KB Output is correct
3 Correct 4 ms 23132 KB Output is correct
4 Correct 10 ms 23172 KB Output is correct
5 Correct 9 ms 23432 KB Output is correct
6 Correct 8 ms 23132 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 8 ms 23128 KB Output is correct
9 Correct 12 ms 23132 KB Output is correct
10 Correct 9 ms 23132 KB Output is correct
11 Correct 9 ms 23132 KB Output is correct
12 Correct 12 ms 23132 KB Output is correct
13 Correct 11 ms 21080 KB Output is correct
14 Correct 1211 ms 60064 KB Output is correct
15 Correct 1272 ms 63544 KB Output is correct
16 Correct 85 ms 34784 KB Output is correct
17 Correct 1076 ms 63272 KB Output is correct
18 Correct 1077 ms 61588 KB Output is correct
19 Correct 1110 ms 63292 KB Output is correct
20 Correct 1091 ms 63012 KB Output is correct
21 Correct 159 ms 38708 KB Output is correct
22 Correct 1160 ms 71108 KB Output is correct
23 Correct 1257 ms 70844 KB Output is correct
24 Correct 1282 ms 70860 KB Output is correct
25 Correct 1230 ms 70844 KB Output is correct
26 Correct 1244 ms 64568 KB Output is correct
27 Correct 1174 ms 64584 KB Output is correct
28 Correct 1168 ms 67796 KB Output is correct
29 Correct 1150 ms 67788 KB Output is correct
30 Correct 1286 ms 66224 KB Output is correct
31 Correct 1252 ms 66228 KB Output is correct
32 Correct 1239 ms 69296 KB Output is correct
33 Correct 1274 ms 69292 KB Output is correct
34 Correct 1223 ms 54780 KB Output is correct
35 Correct 1213 ms 64324 KB Output is correct
36 Correct 434 ms 46204 KB Output is correct
37 Correct 1355 ms 67552 KB Output is correct
38 Correct 1137 ms 69636 KB Output is correct
39 Correct 1225 ms 70852 KB Output is correct
40 Correct 988 ms 60296 KB Output is correct
41 Correct 1211 ms 70856 KB Output is correct
42 Correct 1125 ms 63600 KB Output is correct
43 Correct 1152 ms 63300 KB Output is correct
44 Correct 1398 ms 67624 KB Output is correct
45 Correct 1195 ms 66784 KB Output is correct
46 Correct 1279 ms 70724 KB Output is correct
47 Correct 1022 ms 66608 KB Output is correct
48 Correct 1315 ms 70596 KB Output is correct
49 Correct 959 ms 66496 KB Output is correct
50 Correct 1259 ms 70840 KB Output is correct
51 Correct 1259 ms 64632 KB Output is correct
52 Correct 1260 ms 67804 KB Output is correct
53 Correct 1164 ms 66552 KB Output is correct
54 Correct 1245 ms 69320 KB Output is correct
55 Correct 1232 ms 70740 KB Output is correct
56 Correct 1043 ms 66764 KB Output is correct
57 Correct 1138 ms 63312 KB Output is correct
58 Correct 1074 ms 63304 KB Output is correct
59 Correct 1338 ms 68744 KB Output is correct
60 Correct 1064 ms 66524 KB Output is correct
61 Correct 1264 ms 66248 KB Output is correct
62 Correct 1113 ms 66252 KB Output is correct
63 Correct 1235 ms 69104 KB Output is correct
64 Correct 1040 ms 66560 KB Output is correct