oj.uz

답안 #1049448

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1049448 2024-08-08T18:40:38 Z Edu175 사탕 분배 (IOI21_candies) C++17
100 / 100
 2337 ms 60452 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto fjhg:v)cout<<fjhg<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

struct node{
	ll pre,suf,res,sum,p;
	node(ll i, ll v):p(i){pre=suf=sum=res=v;}
};
node NEUT(-1,0);
node oper(node a, node b){
	auto c=a;
	c.res=max({a.res,b.res,a.suf+b.pre});
	c.pre=max(a.pre,a.sum+b.pre);
	if(c.pre==a.pre)c.p=a.p;
	else c.p=b.p;
	c.suf=max(b.suf,a.suf+b.sum);
	c.sum=a.sum+b.sum;
	return c;
}
struct STree{
	vector<node>t; ll n;
	STree(ll n):t(2*n+5,NEUT),n(n){}
	void upd(ll p, node v){
		for(p+=n,t[p]=v;p>1;p>>=1)p^=p&1,t[p>>1]=oper(t[p],t[p^1]);
	}
	node query(ll l, ll r){
		node izq=NEUT,der=NEUT;
		for(l+=n,r+=n;l<r;l>>=1,r>>=1){
			if(l&1)izq=oper(izq,t[l++]);
			if(r&1)der=oper(t[--r],der);
		}
		return oper(izq,der);
	}
};

vector<STree> st(2,0);
ll n,q;
ll ci;
pair<bool,bool> can(ll p){
	auto res0=st[0].query(p,q).res;
	auto res1=st[1].query(p,q).res;
	// cout<<"can "<<p<<": "<<res0<<" "<<res1<<"\n";;
	return {res0>ci,res1>ci};
}
void upd(ll p, ll v){
	st[0].upd(p,{p,v});
	st[1].upd(p,{p,-v});
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v){
	l.insert(l.begin(),0); r.insert(r.begin(),0);
	v.insert(v.begin(),0);
	n=SZ(c),q=SZ(l);
	st[0]=st[1]=STree(q);
	vector<vector<ii>>upds(n+1);
	fore(i,0,q){
		r[i]++;
		upds[l[i]].pb({i,v[i]});
		upds[r[i]].pb({i,0});	
	}
	vector<int>res(n);
	fore(i,0,n){
		for(auto [p,v]:upds[i])upd(p,v);
		ci=c[i];
		ll l=0,r=q-1;
		while(l<=r){
			ll m=(l+r)/2;
			auto rq=can(m);
			if(rq.fst||rq.snd)l=m+1;
			else r=m-1;
		}
		// cerr<<i<<": "<<l<<" --> ";
		if(r<0)r=0;
		// if(r>=0){
			auto rq=can(r);
			if(rq.fst)res[i]=c[i];
			else res[i]=0;
			ll w=res[i]==0;
			// cout<<"("<<w<<") ";
			l=st[w].query(r,q).p+1;
			// cout<<r<<" r "<<rq.fst<<","<<rq.snd<<"\n";
		// }
		// cerr<<l<<": "<<res[i]<<"\n";
		// fore(h,0,2){
		// 	fore(i,0,q)cout<<st[h].query(i,i+1).sum<<" ";
		// 	cout<<"\n";
		// }
		// cout<<"\n";
		res[i]+=st[0].query(l,q).sum;
		res[i]=min(res[i],c[i]);
		res[i]=max(res[i],0);
	}
	return res;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 7 ms 1044 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1401 ms 58796 KB Output is correct
2 Correct 1615 ms 58036 KB Output is correct
3 Correct 1798 ms 57860 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 385 ms 48164 KB Output is correct
3 Correct 778 ms 10172 KB Output is correct
4 Correct 2337 ms 59884 KB Output is correct
5 Correct 2086 ms 60276 KB Output is correct
6 Correct 1332 ms 60452 KB Output is correct
7 Correct 1307 ms 60012 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 436 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 153 ms 48164 KB Output is correct
4 Correct 564 ms 9020 KB Output is correct
5 Correct 1423 ms 54548 KB Output is correct
6 Correct 1238 ms 56264 KB Output is correct
7 Correct 952 ms 55068 KB Output is correct
8 Correct 1434 ms 57012 KB Output is correct
9 Correct 1903 ms 58100 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 7 ms 1044 KB Output is correct
6 Correct 1401 ms 58796 KB Output is correct
7 Correct 1615 ms 58036 KB Output is correct
8 Correct 1798 ms 57860 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 385 ms 48164 KB Output is correct
11 Correct 778 ms 10172 KB Output is correct
12 Correct 2337 ms 59884 KB Output is correct
13 Correct 2086 ms 60276 KB Output is correct
14 Correct 1332 ms 60452 KB Output is correct
15 Correct 1307 ms 60012 KB Output is correct
16 Correct 0 ms 436 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 153 ms 48164 KB Output is correct
19 Correct 564 ms 9020 KB Output is correct
20 Correct 1423 ms 54548 KB Output is correct
21 Correct 1238 ms 56264 KB Output is correct
22 Correct 952 ms 55068 KB Output is correct
23 Correct 1434 ms 57012 KB Output is correct
24 Correct 1903 ms 58100 KB Output is correct
25 Correct 0 ms 440 KB Output is correct
26 Correct 614 ms 9052 KB Output is correct
27 Correct 364 ms 47908 KB Output is correct
28 Correct 1751 ms 58536 KB Output is correct
29 Correct 1514 ms 58904 KB Output is correct
30 Correct 1385 ms 58912 KB Output is correct
31 Correct 1317 ms 59052 KB Output is correct
32 Correct 1223 ms 59400 KB Output is correct