oj.uz

답안 #821885

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
821885 2023-08-11T19:54:23 Z I_Love_EliskaM_ 사탕 분배 (IOI21_candies) C++17
0 / 100
 2109 ms 48576 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<ll,ll>
#define f first
#define s second

#define int long long
const int inf=1e18;

struct sgt {
	vector<int> lazy;
	vector<int> mn,mx;
	int sz=1;
	sgt(int n) {
		while (sz<n) sz<<=1;
		lazy.assign(4*sz,0);
		mn=mx=lazy;
	}
	pi merge(pi a, pi b) {
		return {min(a.f,b.f), max(a.s,b.s)};
	}
	void push(int v) {
		mn[v]+=lazy[v];
		mx[v]+=lazy[v];
		lazy[2*v+1]+=lazy[v];
		lazy[2*v+2]+=lazy[v];
		lazy[v]=0;
	}
	void add(int v, int l, int r, int lx, int rx, int x) {
		if (lazy[v]) push(v);
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			lazy[v]+=x;
			push(v);
			return;
		}
		int m=(l+r)>>1;
		add(2*v+1,l,m,lx,rx,x);
		add(2*v+2,m,r,lx,rx,x);
		mn[v]=min(mn[2*v+1],mn[2*v+2]);
		mx[v]=min(mx[2*v+1],mx[2*v+2]);
	}
	void add(int l, int r, int x) {
		add(0,0,sz,l,r,x);
	}
	pi query(int v, int l, int r, int lx, int rx) {
		if (lazy[v]) push(v);
		if (rx<=l || r<=lx) return {inf,-inf};
		if (lx<=l && r<=rx) return {mn[v],mx[v]};
		int m=(l+r)>>1;
		auto lq=query(2*v+1,l,m,lx,rx);
		auto rq=query(2*v+2,m,r,lx,rx);
		mn[v]=min(mn[2*v+1],mn[2*v+2]);
		mx[v]=max(mx[2*v+1],mx[2*v+2]);
		return {min(lq.f,rq.f),max(lq.s,rq.s)};
	}
	pi query(int l, int r) {
		return query(0,0,sz,l,r);
	}
};

#undef int

void addqueries(int n, vector<int>&l, vector<int>&r, vector<int>&v) {
	reverse(all(l));
	reverse(all(r));
	reverse(all(v));
	forn(i,2) l.pb(0);
	forn(i,2) r.pb(n-1);
	v.pb(-1e9); v.pb(1e9);
	reverse(all(l));
	reverse(all(r));
	reverse(all(v));
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n=c.size(), q=l.size()+2;
	addqueries(n,l,r,v);

	vector<vector<int>> add(n), del(n);
	forn(i,q) add[l[i]].pb(i), del[r[i]].pb(i);

	sgt st(q);
	vector<int32_t> ans(n);
	forn(i,n) {
		for(auto&x:add[i]) st.add(x,q,v[x]);

		int l=0, r=q-1;
		while (l<r) {
			int mid=(l+r+1)>>1;
			auto x = st.query(mid,q);
			if (x.s - x.f < c[i]) r=mid-1;
			else l=mid;
		}
		auto z = st.query(r,q);
		int t=r;
		l=r+1, r=q-1;
		while (l<r) {
			int mid=(l+r)>>1;
			auto x=st.query(t+1,mid+1);
			if (x.s!=z.s && x.f!=z.f) l=mid+1;
			else r=mid;
		}
		auto x = st.query(r,r+1);
		auto y = st.query(q-1,q);
		z = st.query(t,t+1);
		if (x.f <= z.f) ans[i]=y.f-x.f;
		else ans[i]=c[i]+y.f-x.f;		

		for(auto&x:del[i]) st.add(x,q,-v[x]);
	}
	return ans;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2109 ms 48576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -