Submission #123249

#	Time	Username	Problem	Language	Result	Execution time	Memory
123249		rajarshi_basu	쌀 창고 (IOI11_ricehub)	C++14	68 / 100	1093 ms	119252 KiB

ricehub

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>

#include "ricehub.h"

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define il pair<int,ll>
#define li pair<ll,int>
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,ll>
#define vv vector

using namespace std;

const ll INF = 1e16+10;
const int MAXN = 100*100*10+10;
const int MAXVAL = 1e9+10;

struct Node{
	int left;
	int right;
	ll p1;
	int p2;
	Node(){
		left = -1;
		right = -1;
		p1 = 0;
		p2 = 0;
	}
	void init(){
		left = -1;
		right = -1;
		p1 = 0;
		p2 = 0;
	}
};
Node B[(int)5*1000*1000];
int PTR= 0;
int get__(){
	B[++PTR].init();
	//cout << PTR << endl;
	return PTR;
}
struct Segtree{

	

	int head = get__();
	inline void expand(int node){
		if(B[node].left == -1)B[node].left = get__();
		if(B[node].right == -1)B[node].right = get__();
	}
	void update(int node,int ss,int se,int i,ll val){
		if(i > se or i < ss)return;
		expand(node);
		//cout << node << endl;
		if(ss==se){
			B[node].p1 += val;
			B[node].p2 += 1;
			return;
		}
		int mid = (ss+se)/2;
		update(B[node].left,ss,mid,i,val);
		update(B[node].right,mid+1,se,i,val);
		B[node].p1 = B[B[node].left].p1 + B[B[node].right].p1;
		B[node].p2 = B[B[node].left].p2 + B[B[node].right].p2;
	}
	li get(int node,int ss,int se,int l,int r){
		if(node == -1)return {0,0};
		if(l > se or ss > r)return {0,0};
		if(l <= ss and se <= r)return {B[node].p1,B[node].p2};
		int mid = (ss+se)/2;
		li a = get(B[node].left,ss,mid,l,r);
		li b = get(B[node].right,mid+1,se,l,r);
		return {a.ff+b.ff,a.ss+b.ss};
	}
};
Segtree st;
int besthub(int r,int l,int h[],ll b){

	FOR(i,r){
		st.update(st.head,0,MAXVAL,h[i],h[i]);
	}
	int best = 1;

	FOR(i,r){
		int lo = 0;
		int hi = l+10;
		while(lo <= hi){
			int mid = (lo+hi)/2;

			if(hi - lo < 0){
				FORE(j,lo,hi){
					li cost1 = st.get(st.head,0,MAXVAL,h[i],min(h[i]+j,MAXVAL-1));
					cost1.ff -= (ll)h[i]*cost1.ss;

					li cost2 = st.get(st.head,0,MAXVAL,max(h[i]-j,0),h[i]-1);
					cost2.ff = (ll)h[i]*cost2.ss - cost2.ff;

					if(cost2.ff + cost1.ff <= b){
						best = max(best,cost1.ss+cost2.ss);
					}
				}				
				break;
			}


			int s = h[i]-mid;
			int e = h[i]+mid;

			li cost1 = st.get(st.head,0,MAXVAL,h[i],min(h[i]+mid,MAXVAL-1));
			cost1.ff -= (ll)h[i]*cost1.ss;

			li cost2 = st.get(st.head,0,MAXVAL,max(h[i]-mid,0),h[i]-1);
			cost2.ff = (ll)h[i]*cost2.ss - cost2.ff;
			
			li cc = {0,0};
			li costs = s >= 0? st.get(st.head,0,MAXVAL,s,s) : cc;
			li coste = e <= MAXVAL-1?st.get(st.head,0,MAXVAL,e,e) : cc;
			li csts = {((ll)costs.ss*h[i] - costs.ff) + (coste.ff - (ll)h[i]*coste.ss), costs.ss + coste.ss};

			ll perThingycost = 0;
			ll offset = 0;
			ll prod = 0;
			if(csts.ss > 0){
				perThingycost = csts.ff / csts.ss;

			
				ll left = max((ll)0,(cost2.ff + cost1.ff) - b);
				prod = ceil(left*1.0/perThingycost);
				prod = min(prod,(ll)csts.ss);
				offset = prod*perThingycost;
			}	
			//cout << prod << " " << offset << " " << lo << " " << hi << endl;
			if(cost2.ff + cost1.ff - offset <= b){
				best = max(best,cost1.ss+cost2.ss - (int)prod);
				if(lo == hi)break;
				lo = mid+1;
			}else{
				if(lo == hi)break;
				hi = mid-1;
			}
		}
	}

	return best;
}

int ma1in(){
	int a[5] = {1,2,10,12,14};
	cout << besthub(5,50,a,6) << endl;
	return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 0 / 32