제출 #482972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
482972		MilosMilutinovic	사탕 분배 (IOI21_candies)	C++17	0 / 100	466 ms	109284 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=201000;
int n,q;
VI qs2[N];
vector<PII> qs[N];
ll pref4[N],mn[N],mx[N];
struct node{
	ll valfg,val,mn,mx;
	node() {mn=mx=val=valfg=0;}
}nd[4*N];
void upd(int p) {
	nd[p].mn=min(nd[p*2].mn,nd[p*2+1].mn);
	nd[p].mx=max(nd[p*2].mx,nd[p*2+1].mx);
}
void push(int p) {
	nd[p].val+=nd[p].valfg;
//	nd[p].mn=min(nd[p].mn,nd[p].mn+nd[p].valfg);
//	nd[p].mx=max(nd[p].mx,nd[p].mx+nd[p].valfg);
	nd[p].mn+=nd[p].valfg;
	nd[p].mx+=nd[p].valfg;
	nd[p*2].valfg+=nd[p].valfg;
	nd[p*2+1].valfg+=nd[p].valfg;
	nd[p].valfg=0;
}
//void updval(int p,int l,int r,int tl,int tr,int x) {
//	if (l>r||l>tr||r<tl) return;
//	if (tl<=l&&r<=tr) {
//		nd[p].valfg+=x;
//		push(p);
//		return;
//	}
//	push(p);
//	int md=(l+r)>>1;
//	updval(p*2,l,md,tl,tr,x);
//	updval(p*2+1,md+1,r,tl,tr,x);
//	upd(p);
//}
ll getmn(int p,int l,int r,int tl,int tr) {
	push(p);
	if (l>tr||r<tl) return 1e18;
	if (tl<=l&&r<=tr) return nd[p].mn;
	int md=(l+r)>>1;
	ll L=getmn(p*2,l,md,tl,tr);
	ll R=getmn(p*2+1,md+1,r,tl,tr);
	upd(p);
	return min(L,R);
}
ll getmx(int p,int l,int r,int tl,int tr) {
	push(p);
	if (l>tr||r<tl) return -1e18;
	if (tl<=l&&r<=tr) return nd[p].mx;
	int md=(l+r)>>1;
	ll L=getmx(p*2,l,md,tl,tr);
	ll R=getmx(p*2+1,md+1,r,tl,tr);
	upd(p);
	return max(L,R);
}
ll getval(int p,int l,int r,int x) {
	push(p);
	if (l==r) return nd[p].val;
	int md=(l+r)>>1;
	if (x<=md) return nd[p].valfg+getval(p*2,l,md,x);
	else return nd[p].valfg+getval(p*2+1,md+1,r,x);
}
void modify(int p,int l,int r,int tl,int tr,int x) {
	push(p);
	if (l>tr||r<tl) return;
	if (tl<=l&&r<=tr) {
		nd[p].valfg+=x;
		push(p);
		return;
	}
	push(p);
	int md=(l+r)>>1;
	modify(p*2,l,md,tl,tr,x);
	modify(p*2+1,md+1,r,tl,tr,x);
	upd(p);
}
VI distribute_candies(VI c,VI l,VI r,VI v) {
	n=SZ(c),q=SZ(v);
	VI a(n);
//	if (n<=2000&&q<=2000&&false) {
//		rep(i,0,q) rep(j,l[i],r[i]+1) a[j]+=v[i],a[j]=max(a[j],0),a[j]=min(a[j],c[j]);
//		return a;
//	}
//	bool sb2=true;
//	rep(i,0,q) if (v[i]<0) sb2=false;
//	if (sb2&&false) {
//		rep(i,0,q) {
//			qs2[l[i]].pb(v[i]);
//			qs2[r[i]+1].pb(-v[i]);
//		}
//		ll tot=0;
//		rep(i,0,n) {
//			for (auto x:qs2[i]) tot+=x;
//			a[i]=min((ll)c[i],tot);
//		}
//		return a;
//	}
	bool sb4=true;
	rep(i,0,q) if (l[i]!=0||r[i]!=n-1) sb4=false;
	if (sb4&&false) {
		printf("gas\n");
		pref4[0]=v[0];
		rep(i,1,q) pref4[i]=pref4[i-1]+v[i];
		mx[q-1]=mn[q-1]=pref4[q-1];
		per(i,0,q-1) mx[i]=max(pref4[i],mx[i+1]),mn[i]=min(pref4[i],mn[i+1]);
		rep(i,0,n) {
//			for (auto x:qs[i]) {
//				int id=x.fi;
//				int val=x.se;
//				updval(1,0,q-1,id,q-1,val);
//			}
			if (mx[0]-mn[0]<=c[i]) a[i]=pref4[q-1]-mn[0];
			else {
				int l=0,r=q-1,pos=0;
				while (l<=r) {
					int md=(l+r)>>1;
					if (mx[md]-mn[md]>c[i]) pos=md,l=md+1;
					else r=md-1;
				}
				if (pref4[pos]<pref4[q-1]) a[i]=c[i]-(mx[pos]-pref4[q-1]);
				else a[i]=pref4[q-1]-mn[pos];
			}
		}
		return a;
	}
	rep(i,0,q) {
		qs[l[i]].pb(mp(i+1,v[i]));
		qs[r[i]+1].pb(mp(i+1,-v[i]));
	}
	rep(i,0,n) {
		for (auto x:qs[i]) modify(1,0,q,x.fi,q-1,x.se);
		if (getmx(1,0,q,0,q)-getmn(1,0,q,0,q)<=c[i]) a[i]=getval(1,0,q,q)-getmn(1,0,q,0,q);
		else {
			int l=1,r=q,pos=0;
			while (l<=r) {
				int md=(l+r)>>1;
				if (getmx(1,0,q,md,q)-getmn(1,0,q,md,q)>c[i]) pos=md,l=md+1;
				else r=md-1;
			}
			printf("%d %d %d %d\n",pos,getmx(1,0,q,pos,q),getmn(1,0,q,pos,q),getval(1,0,q,pos+1));
			if (getval(1,0,q,pos)<getval(1,0,q,q)) a[i]=c[i]-(getmx(1,0,q,pos,q)-getval(1,0,q,q));
			else a[i]=getval(1,0,q,q)-getmn(1,0,q,pos,q);
//			rep(j,0,q) printf("%d ",getval(1,0,q-1,j)); puts("");
		}
	}
	return a;
}

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'VI distribute_candies(VI, VI, VI, VI)':
candies.cpp:162:16: warning: format '%d' expects argument of type 'int', but argument 3 has type 'll' {aka 'long long int'} [-Wformat=]
  162 |    printf("%d %d %d %d\n",pos,getmx(1,0,q,pos,q),getmn(1,0,q,pos,q),getval(1,0,q,pos+1));
      |               ~^              ~~~~~~~~~~~~~~~~~~
      |                |                   |
      |                int                 ll {aka long long int}
      |               %lld
candies.cpp:162:19: warning: format '%d' expects argument of type 'int', but argument 4 has type 'll' {aka 'long long int'} [-Wformat=]
  162 |    printf("%d %d %d %d\n",pos,getmx(1,0,q,pos,q),getmn(1,0,q,pos,q),getval(1,0,q,pos+1));
      |                  ~^                              ~~~~~~~~~~~~~~~~~~
      |                   |                                   |
      |                   int                                 ll {aka long long int}
      |                  %lld
candies.cpp:162:22: warning: format '%d' expects argument of type 'int', but argument 5 has type 'll' {aka 'long long int'} [-Wformat=]
  162 |    printf("%d %d %d %d\n",pos,getmx(1,0,q,pos,q),getmn(1,0,q,pos,q),getval(1,0,q,pos+1));
      |                     ~^                                              ~~~~~~~~~~~~~~~~~~~
      |                      |                                                    |
      |                      int                                                  ll {aka long long int}
      |                     %lld

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33